Что было на прошлой лекции

Лекция 3

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

Логически эквивалентные формы порождают одну и ту же истинностную функцию (Доказали?)

Всякая истинностная функция порождается некоторой пропозициональной формой, содержащей лишь связки (доказали и научились строить ДНФ!).

Как строить КНФ? Пример:

х1	х2	f(x1,x2)	ДНФ	КНФ
и	и	л
л	и	и
и	л	л
л	л	и

Для порождения истинностной функции f достаточно любой пары пропозициональных связок из следующих: , или одиночных связок {Конъюнкция отрицаний }, {Штрих Шеффера }

Утверждения:

Д1). ;

Д2).

Д3). Если , то - закон двойственности.

Дата добавления: 2013-12-13