2. Начертить таблицу и заполнить заголовок.

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

3. Заполнить первые 3 столбца.

Количество строк со значениями переменных равно 8.

8:2=4: в 1-м столбце чередуем 4 нуля и 4 единицы.

4:2=2: во 2-м столбце чередуем 2 нуля и 2 единицы.

2:2=1: в 3-м столбце чередуем 1 ноль и 1 единицу.

Таким образом, все возможные комбинации значений переменных учтены и никакие две не совпадают. Фактически такое заполнение столбцов соответствует двоичной записи чисел от 0 до 7.

4. Заполнить остальные столбцы.

Столбцы с 4-го по 7-й заполняем в соответствии с таблицами истинности соответствующих логических операций, причем при заполнении каждого столбца операции выполняются над значениями одного или двух столбцов, расположенных левее заполняемого.

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

1	2	3	4	5	6	7
А	В	С
0	0	0	1	1	1	1
0	0	1	1	0	1	0
0	1	0	0	1	0	1
0	1	1	0	0	0	1
1	0	0	1	1	1	1
1	0	1	1	0	1	0
1	1	0	0	1	1	1
1	1	1	0	0	1	0

Если в формулу входят 4 переменные, то соответствующая ей таблица истинности будет состоять из 2⁴ = 16 строк со значениями; при 5 переменных в таблице имеем 2⁵= 32 строки со значениями.

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

3.2. Тождественно истинные, тождественно ложные и эквивалентные

ВЫСКАЗЫВАНИЯ.

Если высказывание истинно при всех значениях входящих в него переменных, то такое высказывание называется тождественно истинным или тавтологией (обозначается константой 1).

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

Если высказывание ложно при всех значениях входящих в него переменных, то такое высказывание называется тождественно ложным (обозначается 0).

Например, высказывание Сегодня среда, а это – второй день неделиявляется тождественно ложным. Тождественно ложным является следующее высказывание:Компьютер включен, и компьютер не включен (выключен). Математически запись его такова:.

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

Равносильность высказываний АиВзаписывается с помощью знака равенства (=):А = В. ВысказыванияАиВравносильны (А = В)тогда и только тогда, когда их эквивалентностьявляется тождественно истинным высказыванием.

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

Х = Не может быть, что Матроскин выиграл приз и отказался от него.

Y = Или Матроскин не отказался от приза, или не выиграл его.

Чтобы доказать равносильность (эквивалентность) сложных высказываний X и Y, достаточно построить их таблицы истинности. Объединим эти две таблицы в одну:

1	2	3	4	5	6	7	8
А	В			А&B (1)&(2)
0	0	1	1	0	1	1	1
0	1	1	0	0	1	1	1
1	0	0	1	0	1	1	1
1	1	0	0	1	0	0	1

Существует два варианта рассуждений:

1. Так как значения сложных высказываний Х(5-й столбец) иY(6-й столбец) совпадают на всех возможных наборах значений входящих в них переменных, то по определениюXравносильноY.

2. Так как 8-й столбец содержит одни единицы, то эквивалентность ХиYтождественно истинна, значит,ХиYравносильны.

3. ЗАКОНЫ ФОРМАЛЬНОЙ ЛОГИКИ

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

Эти законы являются основными потому, что в логике они играют особо важную роль, являются наиболее общими. Они позволяют упрощать логические выражения и строить умозаключения и доказательства. Первые три из вышеперечисленных законов были выявлены и сформулированы Аристотелем, а закон достаточного основания – Г. Лейбницем.

Закон тождества: в процессе определенного рассуждения всякое понятие и суждение должны быть тождественны самим себе.

Закон непротиворечия: невозможно, чтобы одно и то же в одно и то же время было и не было присуще одному и тому же в одном и том же отношении. То есть невозможно что-либо одновременно утверждать и отрицать.

Закон исключенного третьего: из двух противоречащих суждений одно истинно, другое ложно, а третьего не дано.

Закон достаточного основания: всякая истинная мысль должна быть достаточно обоснована.

Последний закон говорит о том, что доказательство чего-либо предполагает обоснование именно и только истинных мыслей. Ложные же мысли доказать нельзя. Есть хорошая латинская пословица: «ошибаться свойственно всякому человеку, но настаивать на ошибке свойственно только глупцу». Формулы этого закона нет, так как он имеет только содержательный характер. В качестве аргументов для подтверждения истинной мысли могут быть использованы истинные суждения, фактический материал, статистические данные, законы науки, аксиомы, доказанные теоремы.

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

Законы алгебры высказываний (алгебры логики) – это тавтологии.

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

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

Закон тождества: А = А. Всякое понятие и суждение тождественно самому себе.

Закон тождества означает, что в процессе рассуждения нельзя подменять одну мысль другой, одно понятие другим. При нарушении этого закона возможны логические ошибки. Например, рассуждение Правильно говорят, что язык до Киева доведет, а я купил вчера копченый язык, значит, смело могу идти в Киевневерно, так как первое и второе слова «язык» обозначают разные понятия. В рассуждении:Движение вечно. Хождение в школу – движение. Следовательно, хождение в школу вечно слово «движение» используется в двух разных смыслах (первое – в философском смысле – как атрибут материи, второе – в обыденном смысле – как действие по перемещению в пространстве), что приводит к ложному выводу.

Закон непротиворечия: . Не могут быть одновременно истинными суждения и его отрицание. То есть если высказывание А – истинно, то его отрицание не А должно быть ложным (и наоборот). Тогда их произведение будет всегда ложным:. Именно это равенство используется при упрощении сложных логических выражений.

Иногда этот закон формулируется так: два противоречащих друг другу высказывания не могут быть одновременно истинными. Пример невыполнения закона непротиворечия: На Марсе есть жизнь и на Марсе нет жизни.

Закон исключенного третьего: . В один и тот же момент времени высказывание может быть либо неистинным, либо ложным, третьего не дано. Истинно либо А, либо не А.

Примеры выполнения закона исключенного третьего: Число 12345 либо четное, либо нечетное, третьего не дано.Закон исключенного третьего не является законом, признаваемым всеми логиками в качестве универсального закона логики. Этот закон применяется там, где познание имеет дело с жесткой ситуацией: «либо – либо», «истина – ложь». Там же, где встречается неопределенность (например, в рассуждениях о будущем), закон исключенного третьего часто не может быть применим. Рассмотрим следующее высказывание:Это предложение ложно. Оно не может быть истинным, потому что в нем утверждается, что оно ложно. Но оно не может быть и ложным, потому что тогда оно было бы истинным. Это высказывание не истинно и не ложно, а потому нарушается закон исключенного третьего.Парадокс (неожиданный, странный) в этом примере возникает из-за того, что предложение ссылается само на себя. Другим известным парадоксом является задача о парикмахере:В одном городе парикмахер стрижет волосы всем жителям, кроме тех, кто стрижет себя сам. Кто стрижет волосы парикмахеру?В логике из-за ее формальности нет возможности получить форму такого ссылающегося самого на себя высказывания. Это еще раз подтверждает мысль о том, что с помощью алгебры логики нельзя выразить все возможные мысли и доводы.

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

Свойства констант:

(отрицание лжи есть истина)	(отрицание истины есть ложь)
	A&0 = 0
	A&1 = A

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

(отсутствие коэффициентов)

(отсутствие степеней)

Законы коммутативности:

Операнды А и В в операциях дизъюнкции и конъюнкции можно менять местами.

Законы ассоциативности:

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

Законы дистрибутивности:

(дистрибутивность дизъюнкции относительно конъюнкции)

(дистрибутивность конъюнкции относительно дизъюнкции)

Закон дистрибутивности конъюнкции относительно дизъюнкции аналогичен дистрибутивному закону в алгебре, а закон дистрибутивности дизъюнкции относительно конъюнкции аналога не имеет, он справедлив только в логике. Его доказательство удобно провести с помощью таблицы истинности.

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

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

(отрицание вариантов вместе)

(отрицание одновременной истинности)

Словесные формулировки законов де Моргана:

Примеры выполнения закона де Моргана:

1. Высказывание Неверно, что я знаю арабский или китайский языктождественно высказываниюЯ не знаю арабского и не знаю китайского языка.

2. Высказывание Неверно, что я выучил урок и получил по нему двойкутождественно высказываниюИли я не выучил урок,или я не получил по нему двойку.

Правила замены операции импликации:

Правила замены операции эквивалентности:

Интересно их выражение в естественном языке. Например, фраза Если Вини-Пух съел мед, то он сыт тождественна фразе Если Вини-Пух не сыт, то меда он не ел.

Знание правил замены операций импликации и эквивалентности помогает правильно построить отрицание импликации.

Рассмотрим пример. Пусть дано высказывание: Е = Неверно, что если я выиграю конкурс, то получу приз.Пусть А =Я выиграю конкурс, В =Я получу приз.Тогда, т.е. Е =Я выиграю конкурс, но приз не получу.

4. УПРОЩЕНИЕ СЛОЖНЫХ ВЫСКАЗЫВАНИЙ

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

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

	по свойствам констант
	по закону исключенного третьего
	по закону непротиворечия
	по закону идемпотентности
	по закону двойного отрицания

Пример 3.

Требуется упростить:.

По закону дистрибутивности вынесем Аза скобки:.

Пример 4.

Требуется упростить: .

В данном случае воспользуемся законом двойного отрицания.