Главная

Популярная публикация

Научная публикация

Случайная публикация

Обратная связь

ТОР 5 статей:

Методические подходы к анализу финансового состояния предприятия

Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века

Ценовые и неценовые факторы

Характеристика шлифовальных кругов и ее маркировка

Служебные части речи. Предлог. Союз. Частицы

КАТЕГОРИИ:






Полные системы логических знаков




С помощью правила замены мы можем преобразовать формулу таким образом, чтобы она не содержала некоторого логического знака. Например, если дана формула

(p ® q) Ù (r Ú s),

то, применив к ее подформуле (р ® q) правило замены по равносильности (13), получим формулу

(~р Ú q) Ù (r Ú s),

которая равносильна данной, но уже не содержит знака ®.

Так как формулы имеют конечную длину, то каждый из логических знаков может входить в них лишь конечное число раз. Поэтому конечным числом применений правила замены с помощью равносильностей (13), (16) и (17) любую формулу можно преобразовать таким образом, чтобы она не содержала логических знаков, отличных от ~, Ù и Ú. Из полученной формулы также в конечное число шагов с помощью равносильности (14) можно получить формулу, не содержащую знаков, отличных от ~ и Ú, а затем из нее с помощью равносильности (15) можно получить формулу, не содержащую знаков, отличных от ~ и Ù. Наконец, из этой формулы с помощью равносильности (12) можно получить формулу, не содержащую знаков, отличных от ~ и ®.

Рассмотрим в качестве примера преобразование формулы

(p «q) Ù (q ® r) (a)

в формулу, которая равносильна ей, но не содержит знаков, отличных от ~ и Ù. Применяя к подформуле «q) формулы (а) правило замены по равносильности (16), получаем формулу

((~р Ú q) Ù (~q Ú p)) Ú (q ® r). (б)

Затем к подформуле (q ® r) формулы (б) применяем правило замены по равносильности (13) и получаем формулу

((~ р Ú q) Ù (~q Ú p)) Ú (~q Ú r). (в)

Теперь к подформулам (~ р Ú q), (~ q Ú р) и (~ q Ú r) формулы (в) применяем правило замены по равносильности (15) и получаем формулу

(~(~~ р Ù ~q) Ù ~(~~q Ù ~ р)) Ú ~(~~q Ù ~r). (г)

Формула (г), согласно той же равносильности (15), может быть заменена формулой

~(~(~(~~р Ù ~q) Ù ~(~~q Ù )) Ù ~~(~~q Ù ~r), (д)

которая равносильна (а) и не содержит знаков, отличных от ~ и Ù. Применив к формуле (д) четыре раза правило замены по равносильности (1), мы можем получить более простую формулу

~ (~(~ (р Ù ~q) Ù ~ (q Ù )) Ù (q Ù ~r)). (е)

Однако не любой набор логических знаков позволяет выразить через него все остальные. Не любую формулу, например, можно преобразовать в равносильную ей и содержащую одни лишь знаки ~ и «или одни лишь знаки Ù и Ú, или одни лишь знаки Ù, Ú и ®.

Так, с помощью ~ и «нельзя построить формулу, равносильную формуле p ® q, а с помощью Ù, Ú и ® — формулу, равносильную формуле ~р.

В языке логики высказывании имеется, как мы знаем, шесть логических союзов, из которых один — знак отрицания ~ — унарный, т. е. относящийся к одной формуле, и пять — Ù, Ú, ®, «, ¹ — бинарные, т. е. относящиеся к двум формулам. Возникает вопрос, существуют ли еще какие-нибудь логические союзы, смысл которых может быть уточнен с помощью таблиц, заполненных логическими значениями «истина» и «ложь»? Исходя из общих соображений относительно семантики логических знаков, можно предположить существование следующих четырех унарных логических союзов:

 

А 1 A 2 А 3 А 4 А
и и и л л
л и л и л

 

Но знаки —1 и —4 не используются в качестве логических союзов, так как логические значения выражений —1 A и —4 А в заключительном столбце, таблицы не зависят от значений во входном, а логические значения выражения —2 A в заключительном столбце лишь повторяют значения во входном. И только знак —3 есть знак отрицания ~.

Из тех же общих соображений относительно семантики логических знаков можно предположить существование следующих шестнадцати бинарных логических союзов:

 

А   B   А Ñ1 B А Ñ2 B А Ñ3 B А Ñ4 B А Ñ5 B А Ñ6 B А Ñ7 B А Ñ8 B А Ñ9 B А Ñ10 B А Ñ11 B А Ñ12 B А Ñ13 B А Ñ14 B А Ñ15 B А Ñ16 B
и и и и и и л и и л л л и и л л л л
л и и и и л и и л л и и л л и л л л
и л и и л и и л л и л и и л л и л л
л л и л и и и л и и и л л л л л и л

 

Знаки Ñ1 и Ñ16 не используются в качестве логических союзов, так как логические значения выражений A Ñ1 B и A Ñ16 B не зависят от значений А и В во входных столбцах, знаки Ñ6 и Ñ11 не используются в качестве логических постоянных, так как выражения A Ñ6 B и A Ñ11 B не зависят соответственно от А и В и равносильны В и А; знаки Ñ8 и Ñ9 не используются в качестве логических союзов, так как выражения A Ñ8 B и A Ñ9 B не зависят соответственно от А и В и равносильны ~ В и ~А. Остальные десять бинарных логических знаков используются в качестве логических союзов. Знаки Ñ2, Ñ3, Ñ7, Ñ10 и Ñ12 суть логические знаки Ú, ®, «, ¹ и Ù нашего языка. Знаки Ñ4, Ñ5, Ñ8, Ñ13, и Ñ15 используются в качестве логических союзов, но их нет в нашем языке. Они называются соответственно знаками обратной импликации (обознач.), антиконъюнкции (обознач. ­), обратной антиимпликации (обознач. Ü), антиимпликации (обознач. Þ) и антидизъюнкции (обознач. ¯). Если ввести эти знаки в алфавит языка и добавить соответствующие пункты к определению формулы, то формулы (АВ), (А ­ В), (А Ü В), (А Þ В) и (А ¯ В) будут читаться соответственно: А, еслиВ; А несовместно сВ; не А, но В; А, но не В и ниА, ни В.

 

С помощью таблиц легко проверить, что для формул расширенного языка будут иметь место следующие равносильности:

А В равносильно ~ В Ú А; (35 )

А ­ В равносильно ~ А Ú ~ В; (36)

А Ü В равносильно ~(~ В Ú А); (37)

А Þ В равносильно ~(~ А Ú В); (38)

А ¯ В равносильно ~(А Ú В); (39)

~ А равносильно A ­ А; (40)

А Ú В равносильно (А ­ A) ­ (В ­ В ). (41)

Равносильности (13), (16), (17), (14) и (35) — (39) свидетельствуют о том, что из любой формулы языка, расширенной знаками, ­, Ü, Þ и ¯, конечным числом применений правила замены можно получить формулу, не содержащую знаков, отличных от знаков ~ и Ú. Но так как равносильности (40) и (41) позволяют ~ и Ú выразить через антиконъюнкцию ­, то ясно, что любая формула логического языка, содержащего отрицание и все десять бинарных логических знаков, может быть преобразована в равносильную ей формулу, которая не содержит логических знаков, отличных от ­.

Наряду с унарными и бинарными логическими знаками можно вводить логические знаки для различных тернарных и вообще n- арных логических союзов. Из общего числа 256 возможных таблиц для тернарных логических союзов лишь с некоторыми связывают логический знак. Используют, например, тернарный логический союз, который называется условной дизъюнкцией, обозначается знаком 7 и характеризуется следующей таблицей:

А B С A B C
и и и и
л и и л
и л и и
л л и и
и и л и
л и л л
и л л л
л л л л

Имеет место равносильность:

АВС равносильно (А Ú ~ В) Ù (В Ú С), (42)

согласно которой условная дизъюнкция выразима через конъюнкцию, дизъюнкцию и отрицание.

Можно показать, что из какого бы набора унарных, бинарных, тернарных,..., n -арных логических знаков не была построена формула А, существует формула В, которая равносильна А и не содержит знаков, отличных от ~, Ù и Ú.

Так как каждому набору логических значений пропозициональных переменных E 1, Е 2,..., En в таблице формулы А однозначно соответствует логическое значение, зафиксированное в заключительном столбце, то говорят, что формула А определяет логическую функцию F (E 1, Е 2,..., En). Эта функция может быть задана таблицей, которая получается из таблицы формулы А вычеркиванием всех столбцов, кроме входных и заключительного. F (E 1, Е 2,..., En) — двузначная функция, так как пропозициональные переменные и сама функция принимают только два значения:«истина» и «ложь».

Например, формула

p ® (q «r)

определяет логическую функцию F(p, q, r), которая может быть задана также следующей таблицей с перечнем пропозициональных переменных р, q, r:

 

p q r F(p, q, r)
и и и и
л и и и
и л и л
л л и и
и и л л
л и л и
и л л и
л л л и

 

Две равносильные формулы определяют, таким образом, одну и ту же логическую функцию. При условии, что аргументы и функция получают два значения — «истина» и «ложь»— можно построить 2 2n двузначных логических функций n аргументов.

Теорема. Любая логическая функция определяется формулой, содержащей только знаки ~, Ù и Ú.

Доказательство. Пусть F(E 1, Е 2 ,..., En) — функция, заданная таблицей Т. В каждой строке Т зафиксирован набор логических значений пропозициональных переменных E 1, Е 2 ,..., En и соответствующее ему логическое значение F (E 1, Е 2 ,..., En). Занумеруем строки таблицы Т сверху вниз числами 1, 2,…, 2 n.

Пусть формула Вi где i £ 2 n, есть конъюнкция

Сi 1 Ù Сi 2 Ù... Ù Сin,

причем Сij, где (j £ n), есть Еj, если в 1-й строке Т Еj имеет логическое значение «истина», и Сij есть ~ Еj, если в 1-й строке Т Еj имеет логическое значение «ложь». Пусть, далее, формула D есть дизъюнкция всех таких Вi, которые в i -й строке заключительного столбца таблицы Т имеют логическое значение «истина».

Если таких строк в Т нет и в заключительном столбце все строки имеют логическое значение «ложь», то функцию F (E 1, Е 2 ,..., En), заданную Т, определяет формула Ei Ù ~ Ei. Действительно, в заключительном столбце построенной по формуле Ei Ù~ Ei таблицы с перечнем пропозициональных переменных E 1, Е 2,..., En, все строки имеют логическое значение «ложь».

Если же такие строки в Т есть, то заданную таблицей Т функцию F (E 1, Е 2 ,..., En) определяет формула D. Действительно, пусть имеется какой-нибудь набор логических значений переменных E 1, Е 2,..., En и пусть в Т подобный набор логических значений переменных представлен в k- й строке. При данном наборе Bk имеет логическое значение «истина», тогда как все остальные В, имеют при этом наборе логическое значение «ложь». Если для k -й строки Т имеет в заключительном столбце логическое значение «истина», то Вk является дизъюнктом D и, следовательно, при этом наборе D тоже имеет значение «истина». Если для k -й строки Т имеет в заключительном столбце значение «ложь», то Вk не является дизъюнктом D и для рассматриваемого набора логических значений все дизъюнкты D принимают значение «ложь», а следовательно, и вся формула D принимает значение «ложь». Таким образом, формула D определяет функцию F (E 1, Е 2 ,... En).

Пусть, например, дана таблица функции F(p, q, r).

 

р q r F (р, q, r)
и и и л
л и и и
и л и и
л л и л
и и л л
л и л и
и л л л
л л л и

 

Эта функция определяется формулой

(~ p Ù q Ù r) Ú (p Ù ~ q Ù r) Ú (~ р Ù q Ù ~ r) Ú (~р Ù ~ q Ù ~ r).

Из теоремы, в частности, следует, что какова бы ни была формула А и ее таблица Т с перечнем пропозициональных переменных E 1, Е 2 ,..., En, можно построить формулу, равносильную А, но не содержащую других логических знаков, кроме ~, Ù и Ú.

Имея в виду данную теорему говорят, что ~, Ù и Ú образуют полную систему логических знаков. Поскольку же, как мы выяснили выше, каждую формулу, содержащую логические знаки ~, Ù и Ú, можно преобразовать в равносильную ей формулу, не содержащую знаков, отличных от ~ и Ù, то эта пара также образует полную систему логических знаков.

Аналогичным образом полную систему логических знаков образуют пары ~ и Ú, ~ и ®, ® и ¹. Равносильности же (36) и (37) свидетельствуют о том, что знака ­ достаточно для построения формулы, определяющей любую логическую функцию.

Упражнения

I. Из формулы (p ¹ q) ® r

путем равносильных замен получить формулу:

1) не содержащую логических знаков, отличных от ~ и Ù;

2) не содержащую логических знаков, отличных от ~ и Ú;

3) не содержащую логических знаков, отличных от ~ в ®.

II. Найти формулу D, которая содержит только логические знаки ~, Ú и Ù и определяет следующую функцию:

p q r F (p, q, r)
и и и и
л и и и
и л и л
л л и л
и и л и
л и л л
и л л л
л л л и

 

III. Показать, что знака ¯ достаточно для построения формулы, определяющей произвольную логическую функцию.

IV. Найти равносильности, которые свидетельствуют о том,что ® и ¹ образуют полную систему логических знаков (выразить через них ~ и Ú).






Не нашли, что искали? Воспользуйтесь поиском:

vikidalka.ru - 2015-2024 год. Все права принадлежат их авторам! Нарушение авторских прав | Нарушение персональных данных