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

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

Запишем в форме логического выражения составное выска­зывание «(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 B)&(A v В) = (0 v 1)&(1 v 0) = 1 & 1 = 1.

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

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

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

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

Основы логики и логические основы компьютера

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

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

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

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

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

Таблица 3.4. Таблица истинности логической функции F={AvB)&{AvB)

А	в	AvB	А	в	AvB	(AvB)&(AvB) I
						0

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

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

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