Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]


Алгебра высказываний и операции над высказываниями

Алгебра высказываний и операции над высказываниями


Высказывание — первый важнейший объект изучения математической логики. Алгебра высказываний изучает способы построения высказываний из уже имеющихся высказываний, закономерности таких способов сочетания высказываний. Алгебра высказываний является фундаментом математической логики.


Понятие высказывания


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


В дальнейшем будем считать, что имеется первоначальная совокупность некоторых простейших высказываний, называемых элементарными или исходными, о каждом из которых точно известно, истинно оно или ложно. Причем в этой совокупности имеются как истинные высказывания, так и ложные.


Договоримся обозначать конкретные высказывания начальными заглавными буквами латинского алфавита A,B,C,D,\ldots или теми же буквами с индексами внизу.


Приведем примеры высказываний, которые будут использованы в дальнейшем:


A_1\colon "Москва — столица России";
A_2\colon "Саратов находится на берегу Невы";
A_3\colon "Все люди смертны";
A_4\colon "Сократ — человек";
A_5\colon "7 < 4";
A_6\colon "Волга впадает в Каспийское море";
A_7\colon "А.С.Пушкин — великий русский математик";
A_8\colon "Снег белый".

Обозначив истинное высказывание символом 1, а ложное — 0, введем функцию \lambda, заданную на совокупности всех высказываний и принимающую значения в двухэлементном множестве \{0;1\}, по следующему правилу:


\lambda(P)= \begin{cases}1,&\text{if}~~P~~\text{is~true},\\ 0,&\text{if}~~P~~\text{is~false}.\end{cases}

Функция \lambda называется функцией истинности, а значение \lambda(P) — логическим значением или значением истинности высказывания P. Для приведенных высказываний имеем логические значения:


\lambda(A_1)=1,~~ \lambda(A_2)=0,~~ \lambda(A_3)=1,~~ \lambda(A_4)=1,~~ \lambda(A_5)=0,~~ \lambda(A_6)=1,~~ \lambda(A_7)=0,~~ \lambda(A_8)=1.

Отметим, что в литературе имеются следующие обозначения для истинных высказываний: 1, И, t (от англ. true — истинный) и для ложных высказываний: 0, Л, f (от англ. false — ложный). Из этих обозначений будем использовать 1 и 0. Это обусловлено рядом причин. Во-первых, таблицы истинности для формул алгебры высказываний принимают более лаконичный и стандартизированный вид, так как в этом случае наборы значений пропозициональных переменных можно расположить в порядке возрастания чисел, которые этими наборами закодированы в двоичной системе счисления. Например, для случая трех пропозициональных переменных X,\,T,\,Z набор значений этих переменных 000 означает двоичную запись десятичного числа 0, набор 001 — двоичную запись десятичного числа 1, набор 010 — двоичную запись десятичного числа 2, 011 — 3, 100 — 4, 101 — 5, 110 —6, 111 — 7. Во-вторых, более удобный и математически строгий вид принимают многие формулы и алгоритмы алгебры высказываний. В-третьих, обозначение 0 и 1 принято и более целесообразно в приложениях математической логики к компьютерам и информатике.


Из элементарных высказываний с помощью операций над высказываниями или логических связок строят сложные высказывания. Перейдем к точному описанию таких построений.




Отрицание высказывания


Определение 1.1. Отрицанием высказывания P называется новое высказывание, обозначаемое \lnot P (читается: "не P" или "не верно, что P"), которое истинно, если высказывание P ложно, и ложно, если высказывание P истинно. Другими словами, логическое значение высказывания \lnot P связано с логическим значением высказывания P, как указано в следующей таблице, называемой таблицей истинности операции отрицания:


\begin{array}{|c||c|}\hline \lambda(P)& \lambda(\lnot P)\\\hline 0&1\\\hline 1&0\\\hline \end{array}

Здесь может возникнуть вопрос, почему приписывание истинности или ложности высказыванию \lnot P осуществляется именно на основании приведенной таблицы. Конечно, можно ответить, что об определениях не спорят. Но ведь мы желаем построить математическую теорию (алгебру высказываний), которая в какой-то мере отражала бы реально существующий в природе человеческого мышления процесс построения составных высказываний из элементарных и имела бы реальный смысл. Затем мы должны будем развить нашу математическую теорию, а полученные выводы применить в практике мышления и при этом не войти в противоречие с общеизвестными законами мышления. Определение отрицания с помощью приведенной таблицы (как, впрочем, и других логических связок с помощью соответствующих таблиц, о чем речь пойдет далее) появилось как результат длительного опыта, и оно полностью оправдало себя на практике.




Пример 1.2. Применим операцию отрицания к высказыванию A_6\colon "Волга впадает в Каспийское море". Данное отрицание можно читать так: "Неверно, что A_6" т.е. "Неверно, что Волга впадает в Каспийское море". Или же частицу "не" переносят на такое место (чаще всего ставят перед сказуемым), чтобы получилось правильно составленное предложение: "Волга не впадает в Каспийское море". Таблица из определения 1.1 дает для данного высказывания следующее логическое значение: \lambda(\lnot A_6)= \lnot \lambda(A_6)= \lnot1=0, т.е. высказывание \lnot A_6 ложно. Ложность высказывания \lnot A_6 обусловлена только истинностью исходного высказывания A_6 и определением 1.1, но никак не соображениями смысла (содержания) высказывания \lnot A_6. Другое дело, что само определение 1.1 потому и имеет такую формулировку, что оно правильно (или, как говорят, адекватно) отражает факты, известные нам из практики.




Конъюнкция двух высказываний


Определение 1.3. Конъюнкцией двух высказываний P и Q называется новое высказывание, обозначаемое P\land Q или P\And Q (читается: "P и Q"), которое истинно лишь в единственном случае, когда истинны оба исходных высказывания P и Q, и ложно во всех остальных случаях. Другими словами, логическое значение высказывания P\land Q связано с логическими значениями высказываний P и Q, как указано в следующей таблице, называемой таблицей истинности операции конъюнкции:


\begin{array}{|c|c||c|}\hline \lambda(P)& \lambda(Q)& \lambda(P\land Q)\\\hline 0&0&0\\\hline 0&1&0\\\hline 1&0&0\\\hline 1&1&1\\\hline \end{array}

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


Пример 1.4. Применим операцию конъюнкции к высказываниям A_2 и A_3. Получим высказывание A_2\land A_3 л Л3: "Саратов находится на берегу Невы, и все люди смертны". Конечно, мы не воспринимаем это высказывание как истинное из-за первой, ложной, его части. К выводу о ложности полученного высказывания также придем, исходя из логических значений исходных высказываний A_2 и A_3 и определения 1.3 конъюнкции на основании приведенной там таблицы. В самом деле,


\lambda(A_2\land A_3)= \lambda(A_2)\land \lambda(A_3)= 0\land1=0.



Дизъюнкция двух высказываний


Определение 1.5. Дизъюнкцией двух высказываний P и Q называется новое высказывание, обозначаемое P\lor Q (читается "P или Q"), которое истинно в тех случаях, когда хотя бы одно из высказываний P или Q истинно, и ложно в единственном случае, когда оба высказывания P и Q ложны. Другими словами, P\lor Q — такое высказывание, логическое значение которого связано с логическими значениями исходных высказываний P и Q так, как указано в следующей таблице, называемой таблицей истинности операции дизъюнкции:


\begin{array}{|c|c||c|}\hline \lambda(P)& \lambda(Q)& \lambda(P\lor Q)\\\hline 0&0&0\\\hline 0&1&1\\\hline 1&0&1\\\hline 1&1&1\\\hline \end{array}

Пример 1.6. Применим операцию дизъюнкцию к высказываниям A_3 и A_5. Получим составное высказывание A_3\lor A_5\colon "Все люди смертны, или 7&lt;4". Несмотря на первоначально кажущуюся странность этого высказывания, нет сомнений в его истинности. К аналогичному заключению приводит также формальное вычисление логического значения данного высказывания по таблице из определения 1.5, исходя из логических значений высказываний A_3 и A_5:


\lambda(A_3\lor A_5)= \lambda(A_3)\lor \lambda(A_5)= 1\lor0=1.

В то же время высказывание "Саратов находится на берегу Невы, или А. С. Пушкин — великий русский математик", являющееся дизъюнкцией высказываний A_2 и A_7, безусловно, ложно, что полностью согласуется с формальным вычислением его логического значения по таблице из определения 1.5:


\lambda(A_2\lor A_7)= \lambda(A_2)\lor \lambda(A_7)= 0\lor0=0.



Импликация двух высказываний


Определение 1.7. Импликацией двух высказываний P и Q называется новое высказывание, обозначаемое P\to Q (читается: "если P, то Q", или "из P следует Q", или "P влечет Q", или "P достаточно для Q", или "Q необходимо для P"), которое ложно в единственном случае, когда высказывание P истинно, а Q — ложно, а во всех остальных случаях — истинно. Другими словами, логическое значение высказывания P\to Q связано с логическими значениями высказываний P и Q, как указано в следующей таблице, называемой таблицей истинности операции импликации:


\begin{array}{|c|c||c|}\hline \lambda(P)& \lambda(Q)& \lambda()\\\hline 0&0&1\\\hline 0&1&1\\\hline 1&0&0\\\hline 1&1&1\\\hline \end{array}

В высказывании P\to Q высказывание P называется посылкой или антецедентом, а высказывание Q — следствием или консеквентом.


При определении импликации с еще большей силой встает вопрос, почему именно такое распределение принято в ее таблице истинности. Последние две строки в ней достаточно хорошо согласуются с нашим пониманием выражения "если..., то...". Их обоснованием могут служить следующие соображения. Импликация призвана отразить процесс рассуждения, умозаключения. Общая характеристика этого процесса следующая. Если мы исходим из истинной посылки и правильно (верно) рассуждаем, то мы приходим к истинному заключению (следствию, выводу). Другими словами, если мы исходили из истинной посылки и пришли к ложному выводу, значит, мы неверно рассуждали. В импликации P\to Q имеется посылка P, следствие Q и процесс рассуждения \to. Процесс рассуждения как раз и моделируется результатом операции P\to Q. Приведенное соображение служит обоснованием результата 1\to0=0, а также результата 1\to1=1.


Определенные сомнения возникают при оценке адекватности первых двух строк в таблице, определяющей импликацию. В первой строке при ложной посылке и ложном следствии импликация признается истинной. Следующие два примера добавляют аргументы в пользу такого определения логического значения импликации в этом случае. Рассмотрим такое высказывание: "Если число делится на 5, то и его квадрат делится на 5". Его истинность не вызывает сомнения. В частности, мы могли бы сказать: "Если 10 делится на 5, то 10^2 делится на 5" или "Если 11 делится на 5, то и 11^5 делится на 5". В первом из этих высказываний и посылка, и следствие истинны, во втором — и посылка, и следствие ложны. Тем не менее оба этих высказывания истинны. Для большей убедительности второе высказывание можно сформулировать в сослагательной форме: "Если бы 11 делилось на 5, то и 11^2 делилось бы на 5". Есть утверждения такого типа и в житейской речи, которые признаются вполне нормальными. Например, "Если ты можешь переплыть Черное море, то я — турецкий султан".


В пользу второй строки таблицы, когда импликация остается истинной при ложной посылке и истинном следствии, говорит такой пример. Высказывание "Если первое слагаемое делится на 5 и второе слагаемое делится на 5, то и сумма делится на 5", несомненно, истинно. Но, в частности, мы могли бы сказать: "Если 10 делится на 5 и 20 делится на 5, то 30 делится на 5" или "Если 12 делится на 5 и 13 делится на 5, то 25 делится на 5". В первом из этих высказываний и посылка истинна (как конъюнкция двух истинных выражений), и следствие истинно. Во втором же высказывании посылка ложна (как конъюнкция двух ложных высказываний), а следствие истинно. Тем не менее, как мы уже отметили, оба этих высказывания признаются истинными.


Пример 1.8. Высказывание A_6\to A_5: "Если Волга впадает в Каспийское море, то 7&lt;4" ложно, так как


\lambda(A_6\to A_5)= \lambda(A_6)\to \lambda(A_5)= 1\to0=0.

Высказывание "Если Саратов находится на берегу Невы, то А. С. Пушкин — великий русский математик", являющееся импликацией высказываний A_2 и A_7, истинно, так как


\lambda(A_2\to A_7)= \lambda(A_2)\to \lambda(A_7)= 0\to0=1.



Эквивалентность двух высказываний


Определение 1.9. Эквивалентностью двух высказываний P и Q называется новое высказывание, обозначаемое P \leftrightarrow Q (читается: "P эквивалентно Q", или "P необходимо и достаточно для Q", или "P тогда и только тогда, когда Q", или "P, если и только если Q"), которое истинно в том и только в том случае, когда одновременно оба высказывания P и Q либо истинны, либо ложны, а во всех остальных случаях — ложно. Другими словами, логическое значение высказывания P \leftrightarrow Q связано с логическими значениями высказываний P и Q, как указано в следующей таблице, называемой таблицей истинности операции эквивалентности:


\begin{array}{|c|c||c|}\hline \lambda(P)& \lambda(Q)& \lambda(P\leftrightarrow Q)\\\hline 0&0&1\\\hline 0&1&0\\\hline 1&0&0\\\hline 1&1&1\\\hline \end{array}

Пример 1.10. Высказывание "7&lt;4 тогда и только тогда, когда снег белый", являющееся эквивалентностью высказываний A_5 и A_8, ложно, так как


\lambda(A_5\leftrightarrow A_8)= \lambda(A_5) \leftrightarrow \lambda(A_8)= 0\leftrightarrow 1=0.

Напротив, высказывание "Саратов находится на берегу Невы, если и только если А.С.Пушкин — великий русский математик" истинно, так как оно является эквивалентностью двух ложных высказываний.




Союзы языка и логические операции (язык и логика)


Итак, каждая из введенных логических операций является неким математическим образом, моделью соответствующего логического союза нашего языка. Эти понятия призваны отразить на языке нулей и единиц соответствующие союзы нашего мышления, которыми человечество пользуется в течение тысячелетий. Вне всякого сомнения, язык нулей и единиц значительно беднее человеческого языка, и это отражение достаточно грубо и несовершенно. Тем не менее какие-то основные черты (существенные аспекты процессов мышления) понятия логических операций все же отражают. Так, отрицание, конъюнкция и эквивалентность достаточно точно передают суть логических союзов "не", "и", "тогда и только тогда, когда" соответственно. Хуже обстоит дело с дизъюнкцией, призванной отразить языковый союз "или". Следует отметить, что кроме рассматриваемой так называемой дизъюнкции в не исключающем смысле (она истинна тогда и только тогда, когда по меньшей мере один ее член истинен) некоторые авторы рассматривают дизъюнкцию в исключающем смысле (или строгую дизъюнкцию): она истинна тогда и только тогда, когда истинен точно один ее член.


Наименее адекватным соответствующему союзу языка является понятие импликации, которое призвано отразить логический союз "если..., то...". Это и понятно: на этом союзе основан один из сложнейших умственных процессов — процесс построения выводов, умозаключений. Импликация остается все же самой "коварной" из всех логических операций, и ее определение при всех приведенных доводах оставляет в нас чувство незавершенности. И это неспроста. Наиболее наглядно эта неадекватность определения языку проявится в ходе развития алгебры высказываний, когда мы, например, придем к тому, что тавтологией окажется следующая формула: (P\to Q)\lor (Q\to P). Это означает, что какие бы ни были высказывания P и Q, по меньшей мере одно из высказываний P\to Q или Q\to P непременно будет истинным. Этот факт уже не согласуется с общепринятой практикой, и он еще раз подтверждает, что понятие импликации лишь весьма условно и приблизительно переводит на язык нулей и единиц тот смысл, который имеется в виду при построении фразы типа "если..., то...".


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


По поводу происхождениия терминов отметим, что "конъюнкция" происходит от лат. conjunctio — соединение, дизъюнкция — от лат. dusjunctio — разъединение, импликация от лат. implicatio — сплетение и itnplico — тесно связываю.




Общий взгляд на логические операции


Еще раз отметим, что только логические значения или значения истинности, а не их содержание интересуют нас в развиваемой теории. Поэтому каждое из введенных определений (1.1, 1.3, 1.5, 1.7, 1.9) операций над высказываниями можно рассматривать как определение некоторого действия над символами 0 и 1, т. е. как определение некоторой операции на двухэлементном множестве \{0;1\}. Например, отрицание задает следующие правила действия с этими символами: \lnot0=1,~ \lnot1=0, конъюнкция — следующие: 0\land0=0, 0\land1=0, 1\land0=0 1\land1=1, импликация — следующие:


0\to0=1,~~ 0\to1=1,~~ 1\to0=0,~~ 1\to1=1 и т.д.

Учитывая два правила действия с символами 0 и 1, определяемые отрицанием, можно записать равенство для вычисления логического значения высказывания \lnot P:


\lambda(\lnot P)= \lnot \lambda(P).
(1.1)

Указанные четыре правила действия с символами 0 и 1, определяемые конъюнкцией, позволяют записать равенство для вычисления логического значения высказывания P\land Q:


\lambda(P\land Q)= \lambda(P)\land \lambda(Q).
(1.2)

Аналогично, правила действия с символами 0 и 1, сформулированные в определениях 1.5, 1.7, 1.9, дают возможность записать равенства для вычисления логических значений высказываний P\lor Q, P\to Q и P \leftrightarrow Q соответственно:


\lambda(P\lor Q)= \lambda(P)\lor \lambda(Q);
(1.3)

\lambda(P\to Q)= \lambda(P)\to \lambda(Q);
(1.4)

\lambda(P\leftrightarrow Q)= \lambda(P) \leftrightarrow \lambda(Q).
(1.5)

Равенства (1.2) ... (1.5) можно записать в виде одного соотношения: \lambda(P\ast Q)= \lambda(P)\ast \lambda(Q), где значок "\ast" обозначает один из символов логических операций \land,\lor,\to,\leftrightarrow. Равенства (1.1)–(1.5) фактически использовались при вычислениях логических значений высказываний


\lnot A_6,\quad A_2\land A_3,\quad A_3\lor A_5,\quad A_2\lor A_7,\quad A_6\to A_5,\quad A_2\to A_7,\quad A_5\leftrightarrow A_8.

которые были проделаны выше в качестве примеров применения операций над высказываниями.

Математический форум (помощь с решением задач, обсуждение вопросов по математике).
Кнопка "Поделиться"
Если заметили ошибку, опечатку или есть предложения, напишите в комментариях.

Часовой пояс: UTC + 3 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved