Рівносильні перетворення формул

Теорема 3.3. Якщо в формулі деяку її підформулу замінити на рівносильну їй формулу, то одержимо формулу рівносильну даній.

Іншими словами, якщо , то для довільної формули алгебри висловлень має місце рівносильність

Доведення. Оскільки формули і приймають завжди однакові значення при однакових значеннях пропозиціних змінних , то формули

,

приймають однакові значення при однакових наборах значень змінних . Отже,

╞

тобто

.

Використовуючи попередню теорему можемо від однієї формули переходити до рівносильної їй іншої формули. такий перехід називається рівносильним перетворенням формул. Рівносильні перетворення формул застосовуються перш за все для спрощення формул.

Наприклад, формулу можна спростити наступним чином

Рівносильне перетворення формул застосовується також для приведення формул до спеціальних форм (кон’юнктивної нормальної форми, диз’юнктивної нормальної форми), корі мають виключно важливе значення як у самій алгебрі висловлень так і в її застосуваннях.

Зауваження. Якщо деяка формула є тавтологією, то і будь-яка рівносильна їй формула також тавтологія, тобто, якщо ╞ і , то ╞ .

Кожну формулу алгебри висловлень можна шляхом рівносильних перетворень виразити у вигляді різних рівносильних їй формул, які не містять логічних зв’язок → і ↔. Наприклад, формулу можна виразити у вигляді рівносильних їй формул: , , , , , .

Формула, в яку входять лише операції Ù, Ú, Ø називаються зведеними.

Означення. Система пропозиційних операцій S називається повною, якщо будь яка формула еквівалентна формулі, в яку входять лише операції з S.

Теорема 3.4. Системи операцій {Ø, Ú, Ù}, { Ø, Ú} i { Ø, Ù} є повними.

Для доведення цієї теореми достатньо використати рівносильності

, ; (1-й закон де Моргана ); (2-й закон де Моргана ).

Покажемо, наприклад, що система операцій { Ú, Ù, ®} неповна. Дійсно, якщо формула утворена лише із цих операцій і всі пропозиційні змінні приймають значення, рівне одиниці, то . Отже, якщо формула така, що , наприклад , то її неможливо замінити еквівалентною їй формулою, яка б містила лише операції Ú, Ù, ®.

Якщо система операцій неповна, то і будь-яка її підсистема також неповна.

Нехай формула містить лише операції Ø, Ú, Ù. Формула називається двоїстою по відношенню до формули , якщо вона одержується із останньої заміною в ній кожного знаку Ú на Ù і кожного знаку Ù на Ú.