СДНФ. Совершенно дизъюктивная нормальная форма.

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

F= C₁ V C₂ V…V C_s, где C_i –элементарная конъюнкция

Элементарная конъюнкция имеет следующий вид:

C= L₁ & L₂ & … & L_{n ,} где L₁=x или L₁= x.

 

СКНФ. Совершенно конъюктивная нормальная форма.

_{СКНФ – называется представление логической функции в виде конъюнкций элементарных дизъюнкций.}

F= D₁ & D₂ & … & D_n, где D₁ - элементарная дизъюнкция,

Элементарная дизъюнкция имеет следующий вид:

D= L₁ V L₂ V … V L_n, где L₁=x или L₁= x.

Теорема 1. Любая логическая функция может быть представлена в виде СДНФ.

Доказательством теоремы является алгоритм, который позволяет из любой логической функции получить СДНФ.

Пусть логическая функция задана таблицей истинности.

x	y	x	f

 

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

СДНФ: (x & y & z) V (x & y & z) V (x & y & z)

Полученная формула является ДНФ, кроме того она имеет значение совпадающее со значением функции f. Поскольку если мы берем набор, который соответствует значению 1, то какая-то элементарная конъюнкция имеет значение 1.

Противоречивая формула может быть также представлена в ДНФ.

Пример противоречивой формулы в ДНФ:

(x & x) V (y & y) V (z & z)

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

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

 

Теорема 2. Любая логическая функция может быть представлена в виде СКНФ.

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

Пусть логическая функция задана таблицей истинности.

 

x	y	x	f

 

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

СКНФ: (x V y V z) & (x V y V) & (x V y V z) & (x V y V z) & (x V y V z)

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

Противоречивая формула может быть также представлена в КНФ.

Пример противоречивой формулы в КНФ:

(x V x) & (y V y) & (z V z)

Полиномы Жегалкина

F= C ₁ C₂ …. C_n,где - элементарная конъюнкция

Для того, чтобы получить полином, нужно в СДНФ-е выразить «ИЛИ» через «И» / «НЕ» в соответсвии с формулами и затем, с помощью преобразований, привести к соответсвующему виду.

Исчисление высказываний

Общее понятие о логическом исчислении

Для определения логического исчисления необходимо задать:

1. Язык

2. Правила вывода

3. Аксиомы

Рассмотрим пример определения логического исчисления:

1. Язык

a. Алфавит А

b. Формула (будем считать, что в нашем исчислении формулой является произвольная последовательность букв А)

2. Правила вывода

3. Аксиомы: (ноль посылочные правила)

 

Таким образом, мы получили исчисление, в котором может появиться произвольная последовательность букв . Полученное логическое исчисление не является содержательным.

Чтобы исчисление было содержательным оно должно удовлетворять двум требованиям:

1. Правила вывода должны быть корректными (при истинных посылках, истинные следствия)

2. Аксиомы должны быть общезначимы.

Исторически сложившиеся содержательное исчисление высказываний:

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