Логические выражения и таблицы истинности

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

5—2645

Для записи составного высказывания в виде логического выражения на формальном языке (языке алгебры логики) в составном высказывании нужно выделить простые высказы­вания и логические связи между ними.

Запишем в форме логического выражения составное выска­зывание «(2-2 = 5 или 2-2 = 4) и (2- 2*5 или 2-2*4)». Проанализируем составное высказывание. Оно содержит два простых высказывания:

А — * 2-2 = 5» — ложно (0), В = «2 • 2 = 4» — истинно (1).

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

«(А или В) и (А или В)».

Теперь необходимо записать высказывание в форме логи­ческого выражения с учетом последовательности выполне­ния логических операций. При выполнении логических опе­раций определен следующий порядок их выполнения: инверсия, конъюнкция, дизъюнкция. Для изменения ука­занного порядка могут использоваться скобки: F = (A v В) & (A v Б).

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

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

F = (A v В)&(А v Б) = (0 v 1)&(1 v 0) = 1 & 1 = 1.

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

При построении таблиц истинности целесообразно руко­водствоваться определенной последовательностью действий.

Во-первых, необходимо определить количество строк в таблице истинности. Оно равно количеству возможных ком­бинаций значений логических переменных, входящих в ло­гическое выражение. Если количество логических перемен­ных равно п, то:

количество строк = 2".

В нашем случае логическая функция F = (AvB)&(AvB) имеет 2 переменные и, следовательно, количество строк в таблице истинности должно быть равно 4.

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

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

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

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

Таблица 3.4. Таблица истинности логической функцииF= (A v В)&(4 v В) А В AvB А в AvB (AvB)&(AvB) о I

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

Докажем, что логические выражения А & В и AvB равно­сильны. Построим сначала таблицу истинности логического выражения А & В (табл. 3.5).

Таблица 3.5. Таблица истинности логического выражения А& В А В А В А&В

Теперь построим таблицу истинности логического выра­жения AvB (табл. 3.6).

Таблица 3.6. Таблица истинности логического выражения AvB

А	В	AvB	AvB

Значения в последних столбцах таблиц истинности совпа­дают, следовательно, логические выражения равносильны:

А&В = AvB.

Вопросы для размышления

1. Что содержат таблицы истинности и каков порядок их построе­ния?

2. Какие логические выражения называются равносильными?

Ад а н и я

3.2. Записать составное высказывание «(2 •2 = 4и3-3 = 9) или (2-2*4иЗ З* 9)» в форме логического выражения. Постро­ить таблицу истинности.

3.3. Доказать, используя таблицы истинности, что логические вы­ражения A v В и А&В равносильны.

Логические функции

Любое составное высказывание можно рассматривать как логическую функцию F(X_V Х₂, ..., Х_п), аргументами которой являются логические переменные X_v Х₂, ..., Х_п (простые вы­сказывания). Сама функция и аргументы могут принимать только два различных значения: «истина» (1) и «ложь» (0).

Выше были рассмотрены функции двух аргументов: логи­ческое умножение F(A,B) = А&В, логическое сложение F(A,B) = AvB, а также логическое отрицание F(A) = А, в ко­тором значение второго аргумента можно считать равным нулю.

Каждая логическая функция двух аргументов имеет че­тыре возможных набора значений аргументов. По формуле (2.1) мы можем определить, какое количество различных логических функций двух аргументов может существовать:

N = 2⁴ = 16.

Таким образом, существует 16 различных логических функций двух аргументов, каждая из которых задается своей таблицей истинности (табл. 3.7).

Таблица 3.7. Таблицы истинности логических функций двух аргументов Аргу­менты Логические функции А В     F3     F*           F1?   F14   F1fi

Легко заметить, что здесь логическая функция F₂ являет­ся функцией логического умножения, F₈ — функцией логи­ческого сложения, F₁₃ — функцией логического отрицания для аргумента А и F_n — функцией логического отрицания для аргумента В.

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

Логическое следование (импликация). Логическое следо­вание (импликация) образуется соединением двух высказы­ваний в одно с помощью оборота речи «если..., то...».

Логическая операция импликации «если А, то В», обо­значается А —» В и выражается с помощью логической фун­кции F_u, которая задается соответствующей таблицей ис­тинности (табл. 3.8).

Таблица 3.8. Таблица истинности логической функции «импликация» 1 А в f14 = A->B I 1

Составное высказывание, образованное с помо- rj щью операции логического следования (импли­

кации), ложно тогда и только тогда, когда из ис­тинной предпосылки (первого высказывания) сле­дует ложный вывод (второе высказывание).

Например, высказывание «Если число делится на 10, то оно делится на 5» истинно, так как истинны и первое вы­сказывание (предпосылка), и второе высказывание (вывод).

Высказывание «Если число делится на 10, то оно делится на 3» ложно, так как из истинной предпосылки делается ложный вывод.

Однако операция логического следования несколько от­личается от обычного понимания слова «следует». Если пер­вое высказывание (предпосылка) ложно, то вне зависимости от истинности или ложности второго высказывания (выво­да) составное высказывание истинно. Это можно понимать таким образом, что из неверной предпосылки может следо­вать что угодно.

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

Докажем методом сравнения таблиц истинности (табл. 3.8 и 3.9), что операция импликации А -> В равносильна ло­гическому выражению AvB.

Таблица 3.9. Таблица истинности логического выражения AvB

А	в	А	Ave

Таблицы истинности совпадают, что и требовалось дока­зать.

Логическое равенство (эквивалентность). Логическое ра­венство (эквивалентность) образуется соединением двух вы­сказываний в одно с помощью оборота речи «... тогда и толь­ко тогда, когда ...».

Логическая операция эквивалентности «А тогда и только тогда, когда В» обозначается А-В и выражается с помощью логической функции F₁₀, которая задается соответствующей таблицей истинности (табл. 3.10).

Таблица 3.10. Таблица истинности логической функции эквивалентности А В Fw

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

Рассмотрим, например, два высказывания: А = «Компью­тер может производить вычисления» и В = «Компьютер включен». Составное высказывание, полученное с помощью операции эквивалентности, истинно, когда оба высказыва­ния либо истинны, либо ложны:

«Компьютер может производить вычисления тогда и то­лько тогда, когда компьютер включен».

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

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

«Компьютер может производить вычисления тогда и толь­ко тогда, когда компьютер не включен».

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

Вопросы для размышления

1. Какое количество логических функций двух аргументов сущест­вует и почему?

2. Какие логические функции двух аргументов имеют свои назва­ния?

3. Какое существует количество логических функций трех аргумен­тов?

г. * *

3 a jf*aн и я

#1? I

3.4. Доказать, используя таблицы истинности, что операция экви­валентностиА - В равносильна логическому выражению: (Л v В) & (A vВ).

3.5. Логические законы и правила преобразования логических выражений

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

Закон тождества. Всякое высказывание тождественно са­мому себе:

С

Ъ А = А

С?

Закон непротиворечия. Высказывание не может быть одновременно истинным и ложным. Если высказыва­ние А истинно, то его отрицание не А должно быть ложным. Следовательно, логическое произведение высказывания и его отрицания должно быть ложно:

%ft А & А = О

sT

А = А

Закон исключенного третьего. Высказывание может быть либо истинным, либо ложным, третьего не дано. Это означа­ет, что результат логического сложения высказывания и его отрицания всегда принимает значение «истина»:

AvA = 1

а

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

iф'*

Законы де Моргана.

А уВ = А&В А & В = Av В

1SM т

Важное значение для выполнения преобразований логи­ческих выражений имеют законы алгебраических преобра­зований. Многие из них имеют аналоги в обычной алгебре.

>jl

Закон коммутативности. В обычной алгебре слагаемые и множители можно менять местами. В алгебре высказыва­ний можно менять местами логические переменные при опе­рациях логического умножения и логического сложения:

Логическое умножение	Логическое сложение I
А & В= В & А	A v В = A v В I

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

Логическое умножение	Логическое сложение
(А & В) & С = А & (В & С)	(A v В) v С = A v (В v С)

Закон дистрибутивности. В отличие от обычной алгебры, где за скобки можно выносить только общие множители, в алгебре высказываний можно выносить за скобки как об­щие множители, так и общие слагаемые:

Дистрибутивность умножения относительно сложения	Дистрибутивность сложения относительно умножения
ab+ ас = а(Ы-с) — в алгебре (A&B)v(A&C)=A&(BvC)	(A v В) & (A v С) = A v (В & С)

Рассмотрим в качестве примера применения законов ло­гики преобразование логического выражения. Пусть нам не­обходимо упростить логическое выражение:

(А & В) v (А & В).

Воспользуемся законом дистрибутивности и вынесем за скобки А:

(А & В) v (А & В) = А & (В v В).

По закону исключенного третьего В v В =1, следователь­но:

А& (В vB) = А & 1 = А.

3 а

3.5. Доказать справедливость первого A v В = А & В и второго

А & В = A v В законов де Моргана, используя таблицы истин­ности.

3.6. Упростить логические выражения:

а) (A v А) & В; _

б) А & (AvB) & (В v В).

Решение логических задач

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

Условие задачи. В школе-новостройке в каждой из двух аудиторий может находиться либо кабинет информатики, либо кабинет физики. На дверях аудиторий повесили шут­ливые таблички. На первой повесили табличку «По край­ней мере, в одной из этих аудиторий размещается кабинет информатики», а на второй аудитории — табличку с надпи­сью «Кабинет физики находится в другой аудитории». Про­веряющему, который пришел в школу, известно только, что надписи на табличках либо обе истинны, либо обе лож­ны. Помогите проверяющему найти кабинет информатики.

Решение задачи. Переведем условие задачи на язык логи­ки высказываний. Так как в каждой из аудиторий может находиться кабинет информатики, то пусть: А = «В первой аудитории находится кабинет информатики»; В = «Во второй аудитории находится кабинет информатики».

Отрицания этих высказываний: А = «В первой аудитории находится кабинет физики»; В = «Во второй аудитории находится кабинет физики».

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

X = Av В.

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

У = А.

Содержащееся в условии задачи утверждение о том, что надписи на табличках либо одновременно истинные, либо одновременно ложные в соответствии с законом исключен­ного третьего записывается следующим образом: (X & У) v(X & У) = 1.

Подставим вместо X и У соответствующие формулы: (X & У) v (X & У) = ((Л v В) & A) v ((.A v В) & А).

Упростим сначала первое слагаемое. В соответствии с за­коном дистрибутивности умножения относительно сложе­ния:

(A v В) &А = А & A v В & А.

В соответствии с законом непротиворечия: A &Av В &А = 0 v В & А.

Упростим теперь второе слагаемое. В соответствии с пер­вым законом де Мо_ргана и законом двойного отрицания:

(A v В) & А = А &В & А = А & А & Ъ.

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

А&А&В=0&В = 0. В результате получаем:

(О v В & A) v 0 = В & А.

Полученное логическое выражение оказалось простым и поэтому его можно проанализировать без построения табли­цы истинности^ Для того чтобы выполнялось равенство В&А = 1,ВиА должны быть равны 1, то есть соответству­ющие им высказывания истинны.

Ответ: В первой аудитории находится кабинет физики, а во второй — кабинет информатики.

3.7. В процессе составления расписания уроков учителя высказали свои пожелания. Учитель математики высказал пожелание про­водить первый или второй урок, учитель информатики — первый и третий, а учитель физики — второй или третий урок. Сколько существует возможных вариантов расписания и каковы они?