Математическая логика и теория алгоритмов

3) если раскрыть скобки по первому дистрибутивному закону, то получится д.н.ф.; 4) если сгруппировать выражение в скобки, пользуясь вторым дистрибутивным законом, то получится к.н.ф. Легко доказать следующую теорему. Теорема 1.12. Для того, чтобы пропозициональная форма А была тавтологией, необходимо и достаточно, чтобы равносильная ей к.н.ф. содержала в каждом множителе хотя бы одну букву вместе с отрицанием этой же буквы. По теореме 1.12 можно выяснить - выполнима форма Л или нет. Для этого находим к.н.ф. для ~\ АИ если найденная к.н.ф. •- тавтология, то А не выполнима, если же найденная к.н.ф. не тавтология, то форма А выполнима. § 9. Совершенные нормальные формы Совершенной дизъюнктивной нормальной формой (с.д.я.ф.) пропозициональной формы A{Ai,A2, называется д.н.ф. этой фор­ мы, удовлетворяющая следующим условиям: - нет одинаковых слагаемых; - в каждое слагаемое входят все буквы А^Аъ один и только один раз (и только они) с отрицанием либо без отрицания. С.д.н.ф. для А можно построить по таблице истинности этой формы. Для этого выбираем строки, где А равна И; пусть это будут строки ki,k2,...,km. Для каждой выбранной строки hi, 1< i< т, строим элементарное произведение {конституенту edtmuifbi) К, следующим образом: если в выбранной строке ki буква А, принимает значение И, то в Ki она входит без отрицания, если же Aj=JI, то в К, она входит с отрицанием. Дизъюнкция построенных произведений и будет с.д.н.ф. и можно доказать, что эта с.д.н.ф. равносильна^. 34 А В с А{А, В. С.) Л Л •л И Л Л и и Л и л и Л и и л И Л л и И л и л И и л л И и и и