 |
Равносильность формул исчисления высказываний. Конъюнктивная нормальная форма
|
|
|
|
ЛОГИКА ВЫСКАЗЫВАНИЙ
План
ОПРЕДЕЛЕНИЕ ФОРМУЛЫ ИСЧИСЛЕНИЯ ВЫСКАЗЫВАНИЙ
2 АЛГЕБРА ВЫСКАЗЫВАНИЙ
3 РАВНОСИЛЬНОСТЬ ФОРМУЛ ИСЧИСЛЕНИЯ ВЫСКАЗЫВАНИЙ. КОНЪЮНКТИВНАЯ НОРМАЛЬНАЯ ФОРМА
4 ДИЗЪЮНКТИВНАЯ НОРМАЛЬНАЯ ФОРМА. ПРОБЛЕМА РАЗРЕШИМОСТИ
5 СОВЕРШЕННАЯ ДИЗЪЮНКТИВНАЯ НОРМАЛЬНАЯ ФОРМА. СОВЕРШЕННАЯ КОНЪЮНКТИВНАЯ НОРМАЛЬНАЯ ФОРМА
Литература
ОПРЕДЕЛЕНИЕ ФОРМУЛЫ ИСЧИСЛЕНИЯ ВЫСКАЗЫВАНИЙ
Математическая логика стремится к возможно большей точности. Эта цель достигается с помощью точного языка, построенного из устойчивых, наглядно воспринимаемых знаков. В исчислении высказываний используются символы трех сортов:
1. Пропозициональные переменные. Их будем обозначать малыми буквами латинского алфавита с индексами или без них: x, у, х,..., p, q,... Различные буквы обозначают разные суждения, внутренняя структура суждений нас интересовать не будет. Суждения, обозначенные пропозициональными переменными, будут называться высказываниями. Будем полагать, что высказывания удовлетворяют закону исключенного третьего и закону непротиворечия, т.е. каждое высказывание либо истинно, либо ложно. Так что каждая переменная у нас будет принимать два значения: значения «истина» будем обозначать «1», а значение «ложь» – «0».
2. Константы или логические связи – «―», «Ù», «Ú», «®», «º».
3. Скобки: «(» - левая скобка и «)» - правая скобка.
С помощью констант (связок) атомарные высказывания соединяются в более сложные высказывания. Так из двух высказываний p и q с помощью констант образуются высказывания
`p - читается «не-р»
`q - читается «не-q»
pÙq – читается «р и q»
pÚq – читается «р или q»
р®q - читается «если р, то q»
|
|
|
рºq - читается «р тогда и только тогда, когда q»
Сложное высказывание, образованное с помощью знака «¯» называется отрицанием, знака - «Ù» - конъюнкцией, знака «Ú» - дизъюнкцией, знака «®» - импликацией, знака «º» - эквивалентностью. Переменные и сложные высказывания, образованные из них посредствам многократного применения логических связок и скобок называются формулами исчисления высказываний, если они удовлетворяют трем условиям:
1) Пропозициональная переменная есть формула
2) Если φ и ψ – формулы, то (`φ), (`ψ), (φ) Ù (ψ), (φ) Ú (ψ), (φ) ® (ψ), (φ) º (ψ) – формулы. Входящие в эти формулы, формулы (φ) и (ψ) мы будем называть подформулами этих формул.
3) Всякая формула есть либо пропозициональная переменная или образуется из пропозициональных переменных последовательным применением правила 2).
Во избежание ошибок принимаются следующее соглашение об употреблении малых греческих букв φ,ψ,γ,... Эти буквы не являются знаками языка исчисление высказываний и принципиально без них можно было бы обойтись. Они служат лишь для того, чтобы облечь в краткую форму сообщение об исчислении. При таких сообщениях через φ,ψ,γ,... обозначаются любые формулы, точный формальный вид которых остается неопределенным. Так, (φ)®(ψ) заменяет любую формулу, например ((p)Ù(q))→(p) или ((p) → (q))→(p).
Для того, чтобы избежать слишком, большое количество скобок принимаются следующее соглашение:
1) Опускаются скобки, объемлющие отдельные переменные.
2) Полагают, что знак конъюнкций связывает сильнее, чем дизъюнкции и в формулах (φÙψ) Ú γ, γÚ(φÙψ) скобки можно опускать. Аналогичные соглашения принимается относительно других знаков, т.е. считается, что знак «Ù» связывает сильнее, чем знаки «Ú», «®», «º», знак «Ú» сильнее, чем знаки «®», «º», знак «®» сильнее, чем знак «º». Правда, для легкости чтения формул мы будем иногда отступать от этих соглашений.
|
|
|
Из определения подформулы вытекает, что переменные, входящие в формулу, являются ее подформулами; формулы, образованные из этих переменных однократным применением логических связок, вид которых определяется структурой формулы и которые выделяются скобками (а также принятыми относительно их употребления соглашениями), являются подформулами; формулы, образованные из предыдущих подформул таким же однократным применением логических связок являются подформулами и т.д.
АЛГЕБРА ВЫСКАЗЫВАНИЙ
Любая формула алгебры высказываний рассматривается как сложное высказывание, принимающее значение 0,1. В алгебре высказываний решается следующая задача: определить истинностное значение формулы исчисления высказываний для любой комбинации истинностных значений входящих в нее переменных. Для решения этой задачи пользуются следующим алгоритмом.
1) Атомарное высказывание, т.е. переменная, может принимать два значения «1» или «0».
2) Значение формул образованных неоднократным применением логических связок к атомарным высказываниям, задается таблицей:
| р | q | `p | `q | pÙq | pÚq | p→q | p≡q |
| 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 |
3) Для произвольной формулы сначала задаются все комбинации истинностных значений переменных. Затем для каждой комбинации истинностных значений переменных вычисляются значение подформул данной формулы, образованных из переменных однократным применением логических связок, далее вычисляется значение подформул, образованных из предыдущих подформул однократным применением логических связок и т.д. пока в итоге не найдут истинностное значение всей формулы.
Так, пользуясь указанным алгоритмом можно легко вычислить истинностное значение формулы:
((p→q)Ù(q→r))→(p→r)
| p | q | r | p→q | q→r | p→r | (p→q)Ù(q→r) | ((p→q)Ù(q→r) )→(p→r) |
| 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 | 0 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Итак, каждой формуле исчисления высказываний соответствует определенная функция, аргументы которой принимают значение из множества {0,1} и сама она принимает значение из этого множества. Эту функцию называют функцией исчисления высказываний. Проблема разрешимости в алгебре высказываний заключается в решении вопроса, является ли сложная формула тождественно истинной, т.е. истинной при всех значениях входящих в нее переменных, выполнимой, т.е. истинной лишь для некоторого набора значений переменных, или тождественно ложной, т.е. ложной при всех значениях переменных. Это проблема полностью решается посредствам вычисления значения функции, представленной данной формулой, с помощью таблиц истинности.
|
|
|
Функция исчисления высказываний выражает логический закон, если является тождественно истинной при всех возможных значениях переменных. Так, с помощью таблицы убеждаемся, что функция рÚ`p выражается логический закон: закон исключенного третьего:
| р | `р | рÚ`p |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
Аналогичным образом убеждаемся, что функция рÙ`p тоже выражается логический закон: закон непротиворечия:
| р | `p | рÙ` 
| рÙ`p |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
С помощью таблиц истинности можно убедится, что нижеприведенные функции выражают логические законы:
Закон тождества: рºр (1)
Закон отрицания:
для конъюнкции: рÙ`p (2) (закон непротиворечия)
для дизъюнкции: рÚ`p (21) (закон исключенного третьего)
Закон идемпотентности:
для конъюнкции: рÙр º р (3)
для дизъюнкции: рÚ р º р (31)
Закон коммутативности:
для конъюнкции: рÙ q º qÙр (4)
для дизъюнкции: рÚ q º qÚр (41)
Ассоциативный закон:
для конъюнкции: (рÙq) Ù r º p Ù (qÙr) º p Ù qÙr (5)
для дизъюнкции: (рÚq) Úr º pÚ (qÚr) º p Ú qÚr (51)
Дистрибутивный закон:
для конъюнкции дизъюнкций: рÙ(q Ú r) º (p Ùq) Ú (рÙr) (6)
для дизъюнкции конъюнкций: рÚ(qÙ r) º (pÚ q) Ù (рÚr) (61)
Закон поглощения:
для конъюнкции дизъюнкций: рÙ(q Úр) º p (7)
для дизъюнкции конъюнкций: рÚ(q Ù р) º p (71)
Закон двойственности (теорема де Моргана):
|
|
|
для конъюнкции: рÙq º `р Ú`q (8)
для дизъюнкции: рÚq º`р Ù`q (81)
 |
Закон двойного отрицания: `р º р (9)
Уже из внешнего вида формул (1) – (9) отчетливо виден двойственный характер этих законов относительно операций конъюнкции и дизъюнкции: если дана некоторая тождественно истинная функция высказывания, в выражении которой не входит знак «®», то при замене всех входящих в нее знаков «Ú» на «Ù» и «Ù» на «Ú», 1 на 0 и 0 на 1, она остается тождественно истинной. Запишем, например закон противоречия в формуле p Ù`p≡0 применяя к этому выражению закон двойственности, получим закон исключенного третьего p Ú`p≡1 (91)
РАВНОСИЛЬНОСТЬ ФОРМУЛ ИСЧИСЛЕНИЯ ВЫСКАЗЫВАНИЙ. КОНЪЮНКТИВНАЯ НОРМАЛЬНАЯ ФОРМА
Формулы φ и ψ называются равносильными, если формула φ ≡ ψ тождественно истина. Например, формула (p Ù`p) Ú q равносильна q, потому что формула (p Ù`p) Ú q ≡ q тождественно истина (проверку с помощью таблиц истинности предоставляем читателю). Формулы p Ú`p и qÚ`q также равносильны, потому что тождественно истинна формулы p Ú`p ≡ qÚ`q.
Равносильность формул может быть использована для упрощения формул, т.е. для замены какой-то формулы другой формулой, ей равносильной, (эквивалентной), но содержащей либо меньшее число связок, либо меньшее число переменных, либо другие переменные, либо и то, и другое, и третье вместе взятой.
Из определения равносильности формул следует, что тождества (3) - (9) дают нам правила преобразования исходной формулы в новую, ей равносильную к этим правилам добавим и другие правила. Так, любую формулу можно заменить эквивалентной (равносильной) формулой, в которой не содержится знаки «→», «≡» и в которой отрицание опущено лишь на элементарные высказывания. С помощью таблиц истинности можно убедиться в эквивалентности следующих формул:
(р ≡ q) ≡ (р → q) Ù (q→р) (10)
р → q ≡`p Ú q (11)
(р ≡ q) ≡ (`p Ú q) Ù (`qÚр) (12)
(р ≡ q) ≡ (p Ù q) Ú (`рÙ`q) (13)
_____
(р → q) ≡ р Ù`q (14)
р Ù1 ≡ р (15)
р Ù0 ≡ 0 (16)
р Ú0 ≡ р (17)
рÚ 1 ≡ 1 (18)
р Ùq ≡`р Ú `q (19)
р Ú q ≡`рÙ`q (20)
Итак, подобно тому, как в алгебре мы имеем возможность преобразовывать, одно выражение в другое, с какой-то точки зрения более простое (скажем, приводить алгебраическое выражение к удобному для логарифмирования виду, заменять таблицу, задающую определитель, числом и т.д.), мы можем преобразовать составные высказывания. Важное значение в алгебре высказываний имеет преобразование любого составного высказывания к конъюнктивной нормальной форме. Эта нормальная форма состоит из конъюнкции дизъюнкций, где каждый дизъюнктивный член является либо элементарным высказыванием, либо его отрицанием.
|
|
|
На основании установленных эквивалентностей вводим следующие правила:
а1) Со знаками Ú и Ù можно оперировать как в алгебре, пользуясь ассоциативным, коммутативным и дистрибутивным законами;
а2) `р можно заменить р;
а3) р Ùq можно заменить выражением`р Ú `q, а р Ú q - выражением`рÙ`q;
а4) р → q можно заменить выражением `p Ú q, а р ≡ q – выражением (`p Ú q) Ù(`qÚр).
Например, привести к конъюнктивной нормальной форме формулу:
((р Ú q) Ù`q) Ú (rÙq).
Последовательным применением правила а3) получаем:
((р Ú q) Ù`q) Ú (rÙq) ≡((р Ú q) Ù`q) Ù (rÙq) ≡((р Ú q) Ú`q) Ù (`rÚ`q) ≡
≡ ((`рÙ`q) Ú`q) Ù (`rÚ`q).
Применяя к последней формуле закон дистрибутивности, получаем формулу:
(`р Ú `q)Ù(qÙ`q) Ù (`rÚ`q).
Наконец, применяя правило а2) получаем конъюнктивную нормальную форму:
(`р Ú q)Ù(qÚ`q) Ù (`rÚ`q).
Очевидно, что эта форма определяется не однозначно. Так, используя то, что qÚ`q ≡ 1 и (15), получаем другую конъюнктивную нормальную форму первоначальной формулы: (`pÚq) Ù (`rÚ`q)
Запишем обобщения законов поглощения (7):
рÙ(р Ú q1 Ú q2 Ú … Ú qп ) ≡ р (21)
рÚ (р Ù q1Ù q2 Ù… Ù qп ) ≡ р (211)
рÙ(р Ú q1 ) Ù(рÚ q2 ) Ù …Ù (рÚ qп ) ≡ р (22)
рÚ (р Ù q1 ) Ú (рÙ q2 ) Ú … Ú (р Ù qп ) ≡ р (221)
Из них, а также (9), (3), (15)-(18) получаем новые эквивалентности, а значит, правила преобразования, которые позволяют сокращать число переменных, входящих в формулу:
рÚ (qÙ`q) ≡ р (23)
рÙ (qÚ`q) ≡ р (24)
рÚ (qÚ`q) ≡ 1 (25)
рÙ (qÙ`q) ≡ 0 (26)
Используя, справа налево дистрибутивный закон (6), получаем два новых соотношения:
(р Ùq) Ú (р Ù r) ≡ р Ù (q Ú r) (27)
(р Ú q)Ù (р Ú r) ≡ р Ú (q Ù r) (28)
Например, упростить выражение:
(р Ú q Ú r) Ù (рÚ qÚ`r).
Применяя (28), учитывая, что rÙ`r ≡ 0 и (17) получаем:
(р Ú q Ú r) Ù (рÚ qÚ`r) ≡ (р Ú q) Ú (rÙ`r) ≡ р Ú q.
Иногда оказывается полезным для упрощения формулы повторить в ней какие-то выражения, используя, справа налево законы поглощения (21)-(22).
Например, упростить выражение
(р Ú q)Ù (`рÚ q) Ù (`рÚ`q).
Повторим `рÚ q и, используя (6), (2), (17), (4) получаем:
(р Ú q)Ù (`рÚ q) Ù (`рÚ q) Ù (`рÚ`q) ≡ (qÚ(рÙ`р)) Ù (`рÚ (q Ù`q)) ≡ (qÚ0) Ù (`рÚ 0) ≡ qÚ`р ≡ `рÚ q.
Иногда для каких-то целей необходимо вводить в формулу новые переменные (буквы). Это делается с учетом тождеств (24) и (25) и законов дистрибутивности (6). Так, в выражение р Ú q можно ввести букву r. В самом деле, используя (3), а также (6), получаем:
р Ú q≡(р Ú q) Ú (r Ù`r) ≡ (р Ú q Ú r) Ù (рÚ qÚ`r)
|
|
|
