Представление о высказываниях и логических операциях

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

Основным понятием математической логики является понятие простого вы­сказывания.

В алгебре логики все высказывания рассматриваются только с точки зрения их логического значения. Каждое высказывание либо истинно, либо ложно, и ни одно высказывание не может быть одновременно истинным и ложным.

Пример. Волга впадает в Каспийское море. Значение высказывания — «истина».

Лондон — столица Франции. Значение высказывания — «ложно».

Карась не рыба. Значение высказывания — «ложно».

Число 6 делится на 2 и на 3. Значение высказывания — «истина».

Если юноша окончил среднюю школу, то он получает аттестат зрелости. Значение высказывания — «истина».

Предложения «Вперед, гардемарины!» или «Какова сейчас температура воздуха за окном?» не являются высказываниями, поскольку не несут в себе однозначных сведений об истинности или ложности. Таким образом, высказыванием обычно являются повествовательные (но не вопросительные и не восклицательные) предложения.

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

Высказывания, которые получаются из элементарных с помощью граммати­ческих связок «не», «и», «или», «если», «то», «тогда и только тогда», принято на­зывать сложными, или составными. В приведенном примере третье высказывание получается из простого высказывания «Карась — рыба» путем добавления отри­цания «не»; четвертое высказывание образовано из элементарных высказываний «Число 6 делится на 2», «Число 6 делится на 3», соединенных союзом «и». Пятое высказывание получается из простых высказываний «Юноша окончил среднюю школу» и «Юноша получает аттестат зрелости» путем добавления грамматической связки «если ..., то ...». Аналогично, сложные высказывания могут быть получены из простых высказываний путем добавления грамматических связок «или», «тогда и только тогда».

В дальнейшем элементарные высказывания мы будем обозначать малыми бук­вами латинского алфавита; истинное значение высказывания цифрой 1, а ложное значение — цифрой 0. Например, если высказывание а истинно, то будет справед­лива запись а = 1, если высказывание а ложно, то а = 0.

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

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

4.1.2. Соглашения о языке алгебры высказываний

Используются различные обозначения (нотации) как для самих высказываний, так и для операций алгебры высказываний (алгебры логики). Возможные варианты сведены в табл. 4.1.

4.1.3. Логические операции над высказываниями

Над высказываниями можно выполнять следующие логические операции: от­рицание, конъюнкция, дизъюнкция, импликация и эквивалентность.

Операция отрицания высказывания х обозначается х и читается «не х» или «неверно, что х».

Таблицы подобного вида принято называть таблицами истинности.

Пусть х — высказывание. Так как х также является высказыванием, можно образовать отрицание высказывания х, то есть высказывание х, которое называ­ется двойным отрицанием высказываниях. Ясно, что логические значенияхих совпадают.

Пример. Пусть имеется высказывание х «река Волга впадает в Каспийское море». Тогда высказывание «Неверно, что река Волга впадает в Каспийское море» будет отрицанием, то есть х, а высказывание «Неверно, что река Волга не впадает в Ка­спийское море» — двойным отрицанием, то есть f.

Операция конъюнкции высказываний х и у обозначается символом л, а выраже­ние х л у читается «х и у». Высказывания х и у называются членами конъюнкции.

Из определения операции конъюнкции видно, что союз «и» в алгебре логики употребляется в том же смысле, что и в повседневной речи. Но в обычной речи не принято соединять союзом «и» два высказывания, далеких друг от друга по содержанию, а в алгебре логики рассматриваются конъюнкции любых двух вы­сказываний.

Из определения операции конъюнкции и отрицания ясно, что высказывание XAX всегда ложно.

Операция дизъюнкции высказываний х и у обозначается символом v, а вы­ражение xwy читается как «х или у». Высказывания х и у называются членами дизъюнкции.

Логические значения операции дизъюнкции описываются следующей таблицей истинности:

В повседневной речи союз «или» употребляется в различном смысле: исклю­чающем и не исключающем. В алгебре логики союз «или» всегда употребляется в не исключающем смысле.

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

Операция импликации высказываний х и у обозначается символом Э, а вы­ражение х D у читается как «если X_f то у». Высказывание х называют условием, или посылкой, высказывание у — следствием, или заключением, а высказывание х D у — следованием, или импликацией.

Логические значения операции импликации описываются следующей таблицей истинности:

Употребление слов «если..., то...» в алгебре логики отличается от употребления их в обыденной речи, где мы, как правило, считаем, что если высказыванием ложно, то высказывание «Если х, то у» не имеет смысла. Кроме того, строя предложение «Еслих, то г/», мы всегда подразумеваем, что предложение у вытекает из предложе­ниях. Употребление слов «если..., то...» в математической логике не требует этого, поскольку в ней смысл высказываний не рассматривается.

Операция эквивалентности высказываний х и у обозначается символом а выражение х у читается «для того чтобы X_f необходимо и достаточно, чтобы г/» или «х тогда и только тогда, когда у». Высказывания х и у называются членами эквивалентности.

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

Алгебра логики

4.2.1. Понятие формулы алгебры логики

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

(х л у) V z и х D (у V (х д z)).

Первое высказывание есть дизъюнкция конъюнкции X_f у и отрицания выска­зывания z. Второе высказывание есть импликация, посылкой которой является высказывание X_f а заключением — отрицание дизъюнкции высказывания у и конъ­юнкции высказываний X_f г.

Формулы алгебры логики будем обозначать прописными буквами латинского алфавита Л, B_f C_f....

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

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

1. Если высказывание простое, то ему ставится в соответствие элементарная фор­мула.

2. Если высказывание составное, то для составления соответствующей формулы нужно:

1) выделить все элементарные высказывания и логические связки, образующие данное составное высказывание;

2) заменить их соответствующими символами (различные элементарные вы­сказывания обозначатся различными символами);

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

Пример. (х л у) vz = XAyvz — мы опустили скобки, в которые была взята операция дизъюнкции. х D (у V (х л z)) ■ х D у V (х л z) — мы опустили скобки, в которые было заключена формула со знаком отрицания над ней.

Логическое значение формулы алгебры логики полностью определяется ре­зультатом логических операций над значениями входящих в нее элементарных высказываний. Например, логическим значением формулы х л у v z в случае, если X— X_f у — 1,2 = 0, будет истина, то есть х куч Z= 1.

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

Очевидно, что если в формуле п элементарных высказываний, то она принимает 2п значений, состоящих из нулей и единиц, и результирующая таблица содержит 2п строк.

Для формулы таблица истинности имеет вид

4.2.2. Равносильные формулы алгебры логики

Равносильность формул будем обозначать знаком щ тогда запись означает, что формулы А и В равносильны.

Пример. Равносильные формулы:

X M X = X_f (х Л х) V у ■ у.

Тавтологией, или тождественно истинной, называется формула, принимающая значение 1 при всех значениях входящих в нее переменных.

Пример. Тождественно истинные формулы:

XV X_f

х D (х D у).

Тождественно ложной называется формула, принимающая значение 0 при всех значениях входящих в нее переменных.

\

Пример. Тождественно ложная формула: х лх.

Между понятиями равносильности и эквивалентности существует следующая связь: если формулы А и В равносильны, то формула А ** В — тавтология, и об­ратно, если формула Л ** В — тавтология, то формулы АиВ равносильны.

Важнейшие равносильности алгебры логики можно разбить на три группы:

□ основные равносильности;

□ равносильности, выражающие одни логические операции через другие;

□ равносильности, выражающие основные законы алгебры логики.

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

Равносильные преобразования используются для доказательства равносиль- ностей, для приведения формул к заданному виду, для упрощения формул.

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

4.2.3. Основные равносильности

2* ос V ос ⁼ ос»

3. XA I=X.

4. xw Isl.

5. XA 0 = 0.

6. X V 0 S х.

7. XAX = O- закон противоречия.

8. XWX=I- закон исключения третьего.

9. is х— закон снятия двойного отрицания.

10. XA (у wx) =X.

11. XW (у ах) =X.

4.2.4. Равносильности, выражающие одни логические операции через другие

1.(х = у)=_(хЭу)(уЭх).

2.xDy = xw у.

3.XA у = xw у

4.Xwy = XAy

5.XA у = XW у.

6.XW у = X Ay.

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

Дальнейшее исключение логических операций невозможно. Так, если мы будем использовать только конъюнкцию, то уже такая формула, как отрицание х, не мо­жет быть выражена с помощью операции конъюнкции.

Однако существуют операции, с помощью которых может быть выражена любая из пяти логических операций, которыми мы пользуемся. Такой операцией являет­ся, например, операция Штрих Шеффера. Эта операция обозначается символом | и определяется следующей таблицей истинности:

Очевидно, имеют место равносильности:

1. X = х\ X.

2. х лу = (х\у)\(х\у).

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

Отметим также, что х \ у ■ х а у.

4.2.5. Равносильности, выражающие основные законы алгебры логики

1. хлу = у ах — коммутативность конъюнкции.

2. ху у = у у х— коммутативность дизъюнкции.

3. х д (у az) = (х лу) AZ - ассоциативность конъюнкции.

4. хм (ум z) = (хм у) м z — ассоциативность дизъюнкции.

5. х а (у V z) = (х а у) V (х a z) — дистрибутивность конъюнкции относительно дизъюнкции.

6. х V (у a z) = (х V у) а (х V z) — дистрибутивность дизъюнкции относительно конъюнкции.

4.2.6. Решение логических задач методами алгебры

ЛОГИКИ

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

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

1. Антон был вторым, а Борис — пятым.

2. Виктор был вторым, а Денис — третьим.

3. Григорий был первым, а Борис — третьим.

4. Антон был третьим, а Евгений — шестым.

5. Виктор был третьим, а Евгений — четвертым.

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

Обозначим участника первой буквой его имени, нижний индекс около буквы (цифра) будет обозначать номер места, которое он занял в турнире, то есть в вы­ражении X_y имеем, что X — это участник турнира, а у — номер места, которое он занял в турнире. Обозначим буквой L истинное распределение мест в турнире (1 = 1).

Так как в паре высказываний каждого зрителя одно истинно, а второе ложно, то дизъюнкции этих высказываний будут истинными:

A₂ V B₅= 1.

B₂V Д₃ = 1.

Г, VE₃=L

A₃V E₆= 1.

B₃VE_a= 1.

Тогда будет истинной формула

L = (A₂ V E₅) д (B₂ V Д₃) л (Г, V E₃) л (A₃ v E₆) л (B₃ v E₄).

Исходя из данных условия, можно начать преобразования. Поскольку одно из входящих в дизъюнкции высказываний обязательно истинно, а второе обязатель­но ложно, то за отправную точку в преобразованиях можно принять пару T₁ v B₅ = 1. В этой паре высказывание T_t является истинным, a. E₃- ложным, поскольку на первое место нет других претендентов. Тогда, используя равносильность х v О s х_у получаем Г_х v 0 = Г_и и формула приводится к виду

L-^A₂ V -S₅) a (B₂ VД₅)лГ_х л (Л, V E₆) л (B₃ vE₄).

Поскольку вариант E₃ оказался ложным, а других претендентов на пятое место нет, то истинным будет вариант E₅. Тогда в первой по счету паре, применив ту же равносильность, что и на предыдущем шаге, мы также оставляем одно высказы­вание, и основная формула принимает вид

L = E₅ л(B₂ VД₃)АГ₁ л(A₃ V E₆) А(В₃ VE₄).

Продолжая эти равносильные преобразования, приводим формулу к виду

L = E₅ л B₂ a T₁ л A₃ A E₄.

Отсюда следует, что E₅ ■ 1, B₂ = 1, T_t в 1, A₃ = 1, E_i = 1, то есть первым был Григо­рий, вторым — Виктор и т. д. Это и является ответом на вопрос, поставленный в задаче.

4.2.7. Булева алгебра

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

Рассмотрим непустое множество M элементов любой природы (г, г/, 2,...}, в ко­тором определены отношение равенства (=) и три операции: сложение (+), умно­жение (•) и отрицание подчиняющиеся следующим законам:

□ Коммутативные законы:

х + у = у + х; х-у = у -х.

□ Ассоциативные законы:

x+(y+z)-(x + y) + z; x-(y-z) = (x-y)-z.

□ Дистрибутивные законы:

((x + y)-z) = (xz) + (y-z); ((x-y) + z)-(x + z)-(y + z).

□ Законы идемпотентности:

х + х = х;

□ Закон двойного отрицания:

X = X.

□ Законы де-Моргана:

xTy = x-J; х-у = х + у

а Законы поглощения:

х + (г/ • х) = х; х-(у + х) = х.

Такое множество M называют булевой алгеброй.

Если под основными элементами х, г/, Z₁... подразумевать высказывания, под операциями сложения, умножения и отрицания булевой алгебры — соответственно, дизъюнкцию, конъюнкцию и отрицание алгебры высказываний, а знак равенства рассматривать как знак равносильности, то, как следует из равносильностей алге­бры высказываний, все аксиомы булевой алгебры выполняются.

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

Значит, алгебра логики является интерпретацией булевой алгебры. Булева алгебра имеет и другие интерпретации. Например, если под основными элемен­тами X₁ у у Z₁... множества M подразумевать множества, под операциями булевой алгебры — соответственно, объединение, пересечение и дополнение множеств, а под знаком равенства — знак равенства множеств, то мы приходим к алгебре множеств. Нетрудно убедиться, что и в алгебре множеств все аксиомы булевой алгебры выполняются.

Ясно, что тождественно истинные и тождественно ложные формулы алгебры логики представляют собой постоянные функции, а две равносильные формулы выражают одну и ту же функцию.

Каково количество функций п переменных? Очевидно, каждую функцию ал­гебры логики (как и формулу алгебры логики) можно задать с помощью таблицы истинности, которая будет содержать 2п строк. Следовательно, каждая функция п переменных принимает 2п значений, состоящих из нулей и единиц. Таким обра­зом, функция п переменных полностью определяется набором значений из нулей и единиц длины 2п. Общее же количество наборов, состоящих из нулей и единиц длины 2п равно 2²". Значит, количество различных функций алгебры логики п переменных равно 2²".

В частности, различных функций одной переменной четыре, а различных функ­ций двух переменных — шестнадцать. Выпишем все функции алгебры логики одной и двух переменных.

Рассмотрим таблицу истинности для различных функций одной переменной. Она, очевидно, имеет вид

Из этой таблицы следует, что две функции одной переменной будут постоян­ными: Z₁(X) s 1 и f₄(x) = 0, a f₂(x) =х и /₃(г) = х.

Таблица истинности для всевозможных функций двух переменных имеет вид

Ясно, что аналитические выражения этих функций могут быть записаны сле­дующим образом: