ТОР 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 и —4 не используются в качестве логических союзов, так как логические значения выражений —1 A и —4 А в заключительном столбце, таблицы не зависят от значений во входном, а логические значения выражения —2 A в заключительном столбце лишь повторяют значения во входном. И только знак —3 есть знак отрицания ~. Из тех же общих соображений относительно семантики логических знаков можно предположить существование следующих шестнадцати бинарных логических союзов:
Знаки Ñ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 и характеризуется следующей таблицей:
Имеет место равносильность: АВС равносильно (А Ú ~ В) Ù (В Ú С), (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:
Две равносильные формулы определяют, таким образом, одну и ту же логическую функцию. При условии, что аргументы и функция получают два значения — «истина» и «ложь»— можно построить 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).
Эта функция определяется формулой (~ 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, которая содержит только логические знаки ~, Ú и Ù и определяет следующую функцию:
III. Показать, что знака ¯ достаточно для построения формулы, определяющей произвольную логическую функцию. IV. Найти равносильности, которые свидетельствуют о том,что ® и ¹ образуют полную систему логических знаков (выразить через них ~ и Ú). Не нашли, что искали? Воспользуйтесь поиском:
|