Алгебра высказывавнии

 

A	B	Ā
0	0
0	1
1	0
1	1

 

Далее заполняем третий и четвертый столбцы таблицы, соответственно, отрицая высказывания A и B.

 

A	B	Ā
0	0	1	1
0	1	1	0
1	0	0	1
1	1	0	0

 

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

 

A	B	Ā
0	0	1	1	0
0	1	1	0	0
1	0	0	1	1
1	1	0	0	0

 

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

 

A	B	Ā
0	0	1	1	0	1
0	1	1	0	0	1
1	0	0	1	1	1
1	1	0	0	0	0

 

A	B	Ā
0	0	1	1	0	1	0
0	1	1	0	0	1	0
1	0	0	1	1	1	0
1	1	0	0	0	0	1

 

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

Ответ: Таблица истинности сложного высказывания следующая:

 

A	B
0	0	0
0	1	0
1	0	0
1	1	1

 

 

 

 

 

 

 

 

 

Логические законы

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

Закон тождества. Сформулирован древнегреческим философом Аристотелем. Закон утверждает, что мысль, заключенная в некотором высказывании, остается неизменной на протяжении всего рассуждения, в котором это высказывание фигурирует:

 

X=X

 

Закон противоречия говорит о том, что никакое предложение не может быть истинно одновременно со своим отрицанием. "это яблоко спелое" и "это яблоко неспелое".

 

 

Закон исключенного третьего говорит о том, что для каждого высказывания имеются лишь две возможности: это высказывание либо истинно, либо ложно. Третьего не дано. "Сегодня я либо получу 5, либо не получу". Истинно либо суждение, либо его отрицание.

 

 

Закон двойного отрицания заключается в том, что отрицать отрицание какого-нибудь высказывания - то же, что утверждать это высказывание. " Неверно, что 2*2<>4".

 

 

Законы Август де Моргана показывают как отрицаются высказывания:

 

 

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

· отрицание логического произведения эквивалентно логической сумме отрицаний множителей;

· отрицание логической суммы эквивалентно логическому произведению отрицаний слагаемых.

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

операция таблица импликация отрицание

 

Законы коммутативности и ассоциативности говорят о том, что конъюнкция и дизъюнкция аналогичны одноименным знакам умножения и сложения чисел.

 

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

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

 

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

 

 

Законы поглощения показывают как упрощать логические выражения при повторе операнда.

 

 

 

 

 

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

 

Алеша:	"Сосуд греческий и  изготовлен в V в."
Борис:	"Сосуд финикийский  и изготовлен в III в."
Гриша:	"Сосуд не греческий  и изготовлен в IV в."

 

Рассмотрим решение логических задач на следующем примере. Алеша, Боря и Гриша нашли в земле сосуд. Рассматривая удивительную находку, каждый высказал по два предположения:

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

Введем следующие обозначения.

 

Обозначим высказывание:	"Сосуд греческий" буквой Г;
	"Сосуд финикийский" - Ф;
	"Сосуд изготовлен  в V в." - П;
	"Сосуд изготовлен  в III в." - Т;
	"Сосуд изготовлен  в IV в." - Ч.

 

После того, как введены обозначения для простых высказываний, составим сложные высказывания - предположения школьников. Алеша сказал: "Сосуд греческий и изготовлен в V в.". Это сложное высказывание можно записать так: . Из слов учителя следует, что это высказывание ложно. Но Алеша прав в одном из предположений, значит либо Г=1, либо П=1. Значит, истинным будет высказывание (сосуд не греческий, но изготовлен в V в.) или (сосуд греческий, но изготовлен не в V в.). Это рассуждение приводит нас к следующему истинному высказыванию:

 

.

 

Проведя аналогичные рассуждения о высказываниях Бориса и Гриши, мы получим еще два сложных высказывания:

 

.

 

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

 

 

Сосуд не может быть одновременно изготовлен и в третьем и в четвертом веке

 

;

 

Сосуд не может быть одновременно изготовлен и в четвертом и пятом веке

 

;

 

Сосуд не может быть одновременно изготовлен и в третьем и в пятом веке

 

.

 

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

 

;

;

;

.

 

Мы получили семь уравнений над пятью высказываниями Г, Ф, П, Т, Ч. Если все эти высказывания логически перемножить, то мы получим сложное высказывание, в котором сведено воедино все, что говорилось о сосуде. Обозначим это высказывание S(Г, Ф, П, Т, Ч):

 

.(1)

 

Решить задачу - значит указать, при каких значениях высказываний Г, Ф, П, Т и Ч

 

S (Г, Ф, П, Т, Ч) = 1.

 

Сделать это можно, построив таблицу истинности и найдя единственную строку, в которой S (Г, Ф, П, Т, Ч) = 1. Поскольку таблица истинности в данном случае очень большая, её построение можно доверить компьютеру. ( См. Приложение 1). Можно поступить иначе: упростить выражение (1), тогда ответ задачи будет очевиден и без построения таблицы истинности.

 

 

 

 

 

 

 

 

 

Диаграммы Эйлера-Вена

 

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

• построив таблицу истинности для правой и левой частей закона;

• выполнив эквивалентные преобразования над правой и левой частями формулы для приведения их к одному виду;

• с помощью диаграмм Эйлера-Венна.

Леонард Эйлер при решении задач изображал множества с помощью кругов, и в его честь этот метод был назван "методом кругов Эйлера". Однако такой прием очень полезен и при решении логических задач, когда с помощью кругов изображаются высказывания. Стоит отметить, что этим методом математики пользовались и до Эйлера. Так, в трудах Лейбница были обнаружены изображения таких кругов. Но, как уже говорилось, достаточно основательно этот метод был развит Эйлером. После Эйлера метод получил развитие в работах других ученых, однако наибольшего расцвета графические методы достигли в сочинениях английского логика Джона Венна, подробно изложившего их в книге "Символическая логика". Поэтому такие схемы называют "диаграммами Эйлера-Венна".

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

 

 

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