Полные системы функций (связок).

Система функций является полной, если любая n-арная булева функция может быть записана в виде пропозициональной формулы с использованием только функций входящих в эту систему.

Система {¬,∨,∧,→,↔} является полной.

Система {¬,∨,∧} является полной. Именно она и составляет сигнатуру Булевой Алгебры.

Системы {¬,→}, {|} (штрих шеффера), так же полны.

Вторая система – только И-НЕ является важной для микроэлектроники.

Последняя система позволяет представить булевы функции в виде полиномов (полиномов Жигалкина)

Замкнутый класс – это такое множество функций алгебры логики, замыкание которого относительно операции суперпозиции совпадает с ним самим: [P] = P (то есть, любая функция, которую можно записать с помощью только функций входящих в P так же входит в P).

критерий Поста: Система булевых функций является полной тогда и только тогда, когда он не содержится целиком ни в одном из пяти замкнутых классов:

• монотонные функции

}

• функции, сохраняющие нуль

• функции, сохраняющие единицу

• линейные функции

• самодвойственные функции

Если функции содержатся в одном из классов, то и все композиции также не выходят за пределы этого класса (легко проверить для каждого из классов в отдельности) и поэтому система не является полной.

Можно показать, что имея функции по крайней мере из 2 разных классов, можно выразить любую другую функцию.

7. Конъюнктивные и дизъюнктивные нормальные формы. Алгоритмы построения кнф и днф. Теоремы о тождественной ложности и тождественной истинности формул. Дизъюнктивные и конъюнктивные нормальные формы.

Элементарной конъюнкцией называется конъюнкция переменных высказываний и (или) их отрицаний.

Например:

Элементарной дизъюнкцией называется дизъюнкция переменных высказываний и (или) их отрицаний.

Например:

Введём обозначение .

тогда и только тогда, если .

Это позволяет записать элементарные конъюнкции в виде (точнее , но знак конъюнкции обычно опускают), где в качестве значений берётся 0 если входит в конъюнкцию с отрицанием, и 1 если без отрицания. Так же, элементарные дизъюнкции могут быть записаны в виде .

1. тогда и только тогда, если

Элементарная конъюнкция даёт 1 только на наборе переменных, в котором переменные, входящие в неё с отрицанием имеют значение 0, а переменные без отрицания 1.

2. тогда и только тогда, если

Элементарная дизъюнкция даёт 0 только на наборе переменных, в котором переменные, входящие в неё с отрицанием имеют значение 1, а переменные без отрицания 0)

Дизъюнктивной нормальной формой (ДНФ) данной формулы называется равносильная ей формула, представляющая собой дизъюнкцию элементарных конъюнкций.

Например, выражение является ДНФ.

Конъюнктивной нормальной формой (КНФ) данной формулы называется равносильная ей формула, представляющая собой конъюнкцию элементарных дизъюнкций.

Например, выражение – КНФ.

Для того, чтобы построить по данной формуле алгебры логики равносильную ей ДНФ или КНФ необходимо:

1. Перейти в сигнатуру алгебры логики (выразить все операции через дизъюнкцию, конъюнкцию и отрицание),

2. Воспользоваться законом де Моргана для того, чтобы отрицания стояли лишь над элементарными переменными высказываниями,

3. Раскрыть скобки (для построения ДНФ) или воспользоваться дистрибутивным законом (для построения КНФ).

Теорема о тождественной истинности формулы алгебры логики.

Для того, чтобы формула алгебры логики была тождественно истиной, необходимо и достаточно, чтобы каждая элементарная дизъюнкция её конъюнктивной нормальной формы содержала, по крайней мере, одно элементарное переменное высказывание вместе с его отрицанием.

Доказательство.

Пусть каждая элементарная дизъюнкция КНФ, равносильной исходной формуле, содержит некоторую переменную вместе с её отрицанием. Рассмотрим произвольную элементарную дизъюнкцию и пусть в ней содержится некоторая переменная x и её отрицание , тогда, из-за того, что xV =1, эта элементарная конъюнкция будет равна 1. Так для всех элементарных конъюнкций КНФ.

Пусть исходная формула является тождественно истиной. Рассмотрим КНФ ей равносильную и предположим, что в некоторой элементарной дизъюнкции этой КНФ нет пары типа x и . Тогда рассмотрим набор из 0 и 1, такой, что в этом наборе компонента равна 1, если в рассматриваемой элементарной дизъюнкции ей соответствующая переменная входит под знаком отрицания и равна 0, если соответствующая переменная входит без знака отрицания. Тогда на этом наборе элементарная дизъюнкция будет равна 0, тем самым и значение КНФ на этом наборе будет равно 0, что противоречит тожественной истинности исходной формулы.

Теорема о тождественной ложности формулы алгебры логики

Для того, чтобы формула алгебры логики была тождественно ложной, необходимо и достаточно, чтобы каждая элементарная конъюнкция её ДНФ содержала по крайней мере одно элементарное переменное высказывание вместе со своим отрицанием.

Доказательство аналогично доказательству предыдущей теоремы.

Формула алгебры логики f называется логическим следствием формул f₁,f₂,…,f_m, если для любых наборов значений переменных, входящих в формулы, f₁,f₂,…,f_m , f для которых истины все формулы f₁,f₂,…,f_m, формула f тоже истина. Обозначение f₁,f₂,…,f_m f.