ФОРМЫ ПРЕДСТАВЛЕНИЯ ВЫСКАЗЫВАНИЙ Элементарной дизъюнкцией называется выражение вида: Элементарной конъюнкцией называется выражение вида: Где A i - либо элементарное высказывание, либо его отрицание.

Дизъюнктивной нормальной формой (ДНФ) данного высказывания называется равносильное ему высказывание вида: где K i (i=1,s)- элементарная конъюнкция. Конъюнктивной нормальной формой (КНФ) данного высказывания называется равносильное ему высказывание вида: где D i (i=1,t)- элементарная дизъюнкция.

ФОРМЫ ПРЕДСТАВЛЕНИЯ ВЫСКАЗЫВАНИЙ Совершенной дизъюнктивной нормальной формой (СДНФ) данного высказывания называется такая ДНФ, в которой каждая элементарная конъюнкция содержит все элементарные высказывания, либо их отрицания по одному разу. Совершенной конъюнктивной нормальной формой (СКНФ) данного высказывания называется такая КНФ, в которой каждая элементарная дизъюнкция содержит все элементарные высказывания, либо их отрицания по одному разу.

ВВЕДЕМ СЛЕДУЮЩИЕ ОБОЗНАЧЕНИЯ

СДНФ ТЕОРЕМА О СДНФ Всякая не равная тождественному нулю функция f(x 1,x 2,…,x n ) допускает представление ТЕОРЕМА О ЕДИНСТВЕННОСТИ СДНФ Для всякой функции, не равной тождественному нулю существует единственная СДНФ

КАК ПОСТРОИТЬ СДНФ? ДЛЯ КАЖДОГО НАБОРА ЗНАЧЕНИЙ ПЕРЕМЕННЫХ, НА КОТОРЫХ ФУНКЦИЯ ИМЕЕТ ЗНАЧЕНИЕ ПОСТРОИТЬ ЭЛЕМЕНТАРНУЮ КОНЪЮНКЦИЮ, В КОТОРУЮ ВХОДЯТ ВСЕ ПЕРЕМЕННЫЕ, ПРИЧЕМ если значение x i =0, то в конъюнкцию входит отрицание x i, т.е. если значение x i =1, то в конъюнкцию входит само x i, т.е. ОБЪЕДИНИТЬ ПОЛУЧЕННЫЕ ЭЛЕМЕНТАРНЫЕ КОНЪЮНКЦИИ В ДНФ

x y z f

СКНФ ТЕОРЕМА О СКНФ Всякая не равная тождественной единице функция f(x 1,x 2,…,x n ) допускает представление ТЕОРЕМА О ЕДИНСТВЕННОСТИ СКНФ Для всякой функции, не равной тождественной единице существует единственная СКНФ

КАК ПОСТРОИТЬ СКНФ? ДЛЯ КАЖДОГО НАБОРА ЗНАЧЕНИЙ ПЕРЕМЕННЫХ, НА КОТОРЫХ ФУНКЦИЯ ИМЕЕТ ЗНАЧЕНИЕ ПОСТРОИТЬ ЭЛЕМЕНТАРНУЮ ДИЗЪЮНКЦИЮ, В КОТОРУЮ ВХОДЯТ ВСЕ ПЕРЕМЕННЫЕ, ПРИЧЕМ если значение x i =0, то в конъюнкцию входит само x i, т.е. если значение x i =1, то в конъюнкцию входит отрицание x i, т.е. ОБЪЕДИНИТЬ ПОЛУЧЕННЫЕ ЭЛЕМЕНТАРНЫЕ ДИЗЪЮНКЦИИ В КНФ

x y z f

СОКРАЩЕННАЯ ДНФ - ДНФ, ПОЛУЧАЕМАЯ ПОСЛЕ ВСЕХ СКЛЕИВАНИЙ И ПОГЛОЩЕНИЙ ИЗ СДНФ (A&B)U(A&B)=A - склеивание (A&B)UA=A - поглощение

МДНФ -МИНИМАЛЬНАЯ ДНФ (минимальная среди ДНФ) Высказывание из произвольной формы переводится в СДНФ Исходя из СДНФ получают СкДНФ (применив все операции склеивания и поглощения) На основе СДНФ и СкДНФ строится импликантная матрица, с помощью которой получается МДНФ

(xy)U((xUy)&z)= =(x&y&z)U(x&y&z)U(x&y&z)U(x&y&z)&(x&y&z) x&y&z x& y ++ z x&y 4-2 z&y 5-2 x&z 3-4 x&z 3-5 z&y 10-7 z 8-9 z