СКНФ и СДНФ, Логика. Опции

[18192123]

Помогите доказать следующие теоремы:
1. если формула имеет совершенную дизъюнктивную форму, то такая форма единственна.
Вот мои соображения: пусть формула фи имеет 2 различные формы: СДНФ1 и СДНФ2.
пусть некая элементарная конъюнкция СДНФ1 не содержится в сДнф2. Дальше ... не знаю....наверное задать литералам (элементарным высказываниям или их отрицаниям), вход. в эту элементарн. конъюнкцию, какие-то значения.....

???

2. Доказать, что тождественно-истинная и тождественно-ложная фомулы не имеют совершенных форм.
Мне кажется, что исходить нужно из того, что каждый литерал ( элементарное высказывание или его отрицание) входит по 1 разу в элементарн. дизъюнкцию или конъюнкцию.....

Сообщение отредактировано: 18192123 - 9.04.2007 18:33

[КМА]

Доказать, что тождественно-истинная и тождественно-ложная фомулы не имеют совершенных форм.

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

Соответственно, если мы отрицаем тождественно истинную формулу, то получим тождественно ложную, и тогда пользуясь равносильностью: *(AB)=*A+*B, мы перейдем к СКНФ, а ввиду того, что содержание всех возможных дизъюнктов (это для СДНФ) есть в 1 части доказательства, то получаем все возможные варианты (но уже конъюнктов).