3.1.3. Полнота в логике высказываний

3.1.3.1. Эквивалентные замены логических связок

Рассмотрим вопрос о минимальном количестве логических связок, необходимых для выражения любого высказывания, образованного с помощью определенных нами выше логических связок. Известно, что можно выразить как , так что использовать удобно, но не необходимо. К тому же эквивалентно .

Также эквивалентно , поэтому нет необходимости использовать , если применяется ~ и . Кроме того, эквивалентно и эквивалентно . Следовательно, любое высказывание может быть выражено через пару связок ~ и или ~ и , причем в любом случае необходимы обе связки. Однако существуют две связки, обладающие тем свойством, что любое высказывание может быть выражено с использованием только одной из них. Эти связки: | – так называемый штрих Шеффера и — так называемая стрелка Пирса (стрелка Пирса также иногда обозначается как ). Свои названия эти связки получили в честь математиков Г.Шеффера и Ч.Пирса. Этим связкам соответствуют таблицы истинности

Случай p q 1 T T F 2 T F T 3 F T T 4 F F T

Случай p q 1 T T F 2 T F F 3 F T F 4 F F T

Для того, чтобы показать, что любую связку можно заменить одной лишь связкой | или только связкой , достаточно показать это для пар связок ~ и или ~ и , поскольку возможность выразить любую связку одной из этих пар уже показана. Эквивалентность и устанавливается при помощи следующей таблицы истинности:

Случай	p	p	|	p
1	T	T	F	T
2	F	F	T	F
			*

Аналогично, при помощи таблиц истины, доказывается.

,

.

Также, если показать, что ~ и или ~ и можно выразить, используя только , тогда и любую связку можно выразить, используя лишь . Аналогично предыдущему случаю доказательству эквивалентно . Также доказывается

,

.

Также заметим, что

.

Поэтому в дальнейшем связка | будет называться не-и или и-не, а связка будет называться не-или или или-не.

Пример 1. Представить логическими формулами следу­ющие высказывания:

1. "Сегодня понедельник или вторник".

2. "Идет дождь или снег".

1. "Если идет дождь, то крыши мокрые. Дождя нет, а кры­ши мокрые".

4. "Что в лоб, что по лбу".

1. Составное (сложное) высказывание "Сегодня поне­дельник или вторник" состоит из двух простых:

А – «Сегодня понедельник»;

В – «Сегодня вторник».

Высказывания А, В соединены связкой "или" очевидно в разделительном смысле, т.е. - . Таким образом, данное выс­казывание представимо логической формулой:

А В

2. Высказывание "Идет дождь или снег" состоит из двух простых:

А – «Идет дождь»;

В – «Идет снег».

Но в отличие от предыдущего о связка ''или'' использована здесь не в разделительном смысле, поэтому логическая формула имеет вид:

А В

3. Сложное высказывание «Если идет дождь, то крыши мокрые. Дождя нет, а кры­ши мокрые» включает два простых высказывания:

А – «Идет дождь»,

В – «Крыши мокрые».

В первом высказывании «Если идет дождь, то крыши мокрые» высказывания А и В соединены связкой следования:

А→В

Во втором «Дождя нет, а кры­ши мокрые» высказывания А и В связаны связкой «и», кроме того первое следует взять с отрицанием:

А&B

Остается объединить два полученных выше высказывания в одно связкой «и»

(А В)&( А&B)

4. Высказывание «Что в лоб, что по лбу» содержит два простых:

А – «В лоб»,

В – «По лбу»,

Представимо формулой:

А~В

Пример 2. Записать логическими формулами следующие сложные высказывания:

1 . "Если допоздна работаешь с компьютером и при этом пьешь много кофе, то утром просыпаешься в дурном распо­ложении духа или с головной болью".

2. "Если социологические исследования показывают, что потребитель отдает предпочтение удобству и многообразию выбора, то фирме следует сделать упор на усовершенствова­ние товара или увеличение многообразия новых форм".

1 . Первое составное высказывание состоит из следую­щих простых:

Х – "Допоздна работаешь с компьютером".

Y – "Пьешь много кофе".

Z – "Утром встаешь в дурном расположении духа".

U – "Утром встаешь с головной болью".

Оно может быть представлено в виде следующей логи­ческой формулы:

(X&Y)→(Z U)

2. Второе составное высказывание состоит из следующих простых:

Х – "Социологические исследования показывают, что по­требитель отдает предпочтение удобству".

Y –"Социологические исследования показывают, что по­требитель отдает предпочтение многообразию выбора".

Z – "Фирме следует сделать упор на усовершенствование товара".

U – "Фирме следует сделать упор на увеличение многооб­разия новых форм".

Логическая формула второго составного высказывания:

(X&Y)→(Z U)

Пример 3. Записать формулами логики высказываний два способа доказательства равенства множеств:

1. Множества X и Y равны, если для любого элемента a из того, что а принадлежит Х, следует, что а принадлежит Y, и из того, что а не принадлежит Х, следует, что а не принадлежит Y:

2. Множества X и Y равны, если для любого элемента a из того, что а принадлежит Х, следует, что а принадлежит Y, и из того, что а принадлежит Y, следует, что а принадлежит Х.

Обозначим простые высказывания:

А – «Элемент а принадлежит Х, т.е. а Х»,

В – «Элемент а принадлежит Y, т.е. а Y»,

С – «Множества X и Y равны, т.е. X=Y».

Тогда процедура доказательства, исходя из первого определения:

«Если из А следует В, и из А следует В, то С» или:

((А→В)&( A→ B))→C

Второе определение представимо следующей формулой:

«Если из А следует В, и из В следует А, то С» или:

((А→В)&(В→А))→C