Основы логики

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

Логика это наука о формах и способах мышления. К формам мышления можно отнести понятие, высказывание и умозаключение.

Понятие это выделение одного объекта от других по определённым признакам, параметрам свойствам.

Высказывание — суждение или повествовательное предложение, в котором что-то утверждается или отрицается.

Умозаключение это форма мышления, благодаря которой из двух или более суждений получается ещё одно суждение, которое является выводом. Оба первоначальных суждений, должны быть истинными и их называют условием к получению вывода. Между этими суждениями должна быть связь. Третье суждение это вывод он же является следствием и в зависимости от вида умозаключения может быть истинным или ложным.

Виды умозаключений: индукция, дедукция.

Дедукция: рассуждение или переход от общего правила к частному. Вывод всегда истинный.

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

Рассмотрим примеры дедукции и индукции:

Дедукция	Индукция
Все металлы электропроводны. Алюминий проводит ток. Алюминий металл.	Алюминий проводит ток. Железо, Медь, Цинк, Свинец тоже проводят ток. Все металлы электропроводны.(Истина).
Все птицы-млекопитающие(ложь). Голубь птица. Все голуби млекопитающие(ложь).	Алюминий твёрдое тело. Железо, Медь, Цинк, Свинец тоже твёрдые тела. Все металлы твёрдые.(Ложь. Ртуть метал, но жидкий).
Все латиноамериканские страны – республики. Бразилия, Аргентина – латиноамериканские страны. Бразилия, Аргентина – республики.	Бразилия, Аргентина – республики. Бразилия, Аргентина – латиноамериканские страны. Все латиноамериканские страны – республики (Истина).
Все птицы кладут яйца. Все птицы позвоночные. Некоторые позвоночные кладут яйца.	Италия, Франция являются республиками. Италия, Франция европейские страны. Все европейские страны республики (Ложь.)
	Змеи не имеют ног. Змеи животные. Некоторые животные не имеют ног.

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

• Все студенты – учащиеся
• Этот человек – студент
• Этот человек – учащийся

Сначала мы говорим о всех студентах, затем связываем некоего человека со студентом всё хорошо. НО, если связи нет, получится неправильное строение умозаключения, из которого может получится(хотя и не всегда) неправильный вывод. Поменяем местами второе и третье высказывание:

• Все студенты – учащиеся
• Этот человек – учащийся
• Этот человек – студент

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

Бывают случаи, когда при неправильном строении условия, чисто случайно может получиться правильный вывод:

• Резина не проводит электричество
• Вода не резина
• Вода проводит электричество

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

Даны высказывания, по ним сделать вывод:

• Все певцы знают ноты
• Фёдор Шаляпин певец
• Значит …

• Настоящие водители, знают ПДД
• Иванов настоящий водитель
• Значит …

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

Инверсия

это логическое отрицание соответствует русской частице НЕ, обозначается ещё ¬, A, Not. Она заменяет истинное высказывание на ложное и наоборот. Унарная(одноместная) т.е. отрицает какое то одно высказывание.

1. (2 × 2 = 4) — ИСТИНА или TRUE или 1
2. ¬(2 × 2 = 4) — ЛОЖЬ или FALSE или 0
3. (2 × 2 = 5) — ЛОЖЬ или FALSE или 0
4. (2 × 2 = 5) — ИСТИНА или TRUE или 1

Таблица истинности логического отрицания:

A	F = A
0	1
1	0

Конъюнкция

это логическое умножение соответствует русскому союзу И, обозначается &, Λ, And. Истинное значение будет только при истинности обоих операндов, все остальные ложь. Бинарная(двуместная).

• (2 × 2 = 5) & (3 × 3 = 8) = ЛОЖЬ
• (2 × 2 = 5) & (3 × 3 = 9) = ЛОЖЬ
• (2 × 3 = 6) Λ (2 × 4 = 8) = ИСТИНА
• (2 × 2 = 4) Λ (3 × 3 = 9) = ИСТИНА

Таблица истинности логического умножения

A	B	F = A Λ B
0	0	0
0	1	0
1	0	0
1	1	1

это логическое сложение соответствует русскому союзу ИЛИ, обозначается |, V, Or. Ложное значение будет только при ложности обоих операндов, все остальные истина. Бинарная(двуместная).

• (2 × 2 = 5) | (2 × 4 = 8) = ИСТИНА
• (2 × 2 = 5) | (2 × 3 = 9) = ЛОЖЬ
• (2 × 2 = 4) V (2 × 3 = 6) = ИСТИНА
• (2 × 2 = 4) V (3 × 3 = 1) = ИСТИНА

Таблица истинности логического умножения:

A	B	F = A V B
0	0	0
0	1	1
1	0	1
1	1	1

Из этих трёх простых логических операций, строят множество других сложных логических операции, мы рассмотрим две из них: импликация и эквивалентность

это логическое следование образуется соединением двух высказываний в одно с помощью оборота речи ЕСЛИ .. ТО, обозначается →, ложно тогда, когда из истиной предпосылки 1-го высказывания следует ложный вывод. Бинарная(двуместная).

A V B = А → B

Таблица истинности логического следования:

A	B	F = A → B
0	0	1
0	1	1
1	0	0
1	1	1

Для понимания смысла импликации может пригодиться житейская модель: А — начальник. Он может приказать «работай» (1) или сказать «делай что хочешь» (0). В — подчиненный. Он может работать (1) или бездельничать (0). В таком случае импликация — не что иное, как послушание подчиненного начальнику. По таблице истинности легко проверить, что послушания нет только тогда, когда начальник приказывает работать, а подчиненный бездельничает.

Ещё житейский пример импликации: A(Идёт дождь), B(раскрыть зонтик), результат ложь если человек намокнет. Человек будет мокрым в одном случае, если будет идти дождь, и он не раскроет зонтик.

это логическое равенство образуется соединением двух высказываний в одно с помощью оборота речи ТОГДА И ТОЛЬКО ТОГДА, обозначается ↔, ~, истинно когда оба высказывания одновременно либо истинны, либо ложны. Бинарная(двуместная).

(A Λ B) V (A Λ B) = A ↔ B

Таблица истинности логического равенства:

A	B	F = A ↔ B
0	0	1
0	1	0
1	0	0
1	1	1

Для понимания эквивалентности удобны два высказывания: А = «Компьютер вычисляет» и В = «Компьютер включён».

При составлении логических условий поиска в базах данных, легко ошибиться. Например, в базе данных БИБЛИОТЕКА есть сведения о книгах разных авторов, то при выборе всех книг Лермонтова и Есенина хочется в условии выбора поставить (Лермонтов И Есенин), но мы получим результат книг автором которых будет и тот, и другой автор, чего не может быть. Нужно заменить логическую операцию (И) на (ИЛИ) — (Лермонтов ИЛИ Есенин).

Выполним задание на обработку сложных условий.

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

№	A	B	C	Условие	Ответ
R1	1	2	3	A=1 & B=2	R1
R2	1	3	1	A=1 | A=3	R1 R2 R4 R5
R3	2	2	2	A=1 | B=2	R1 R2 R3 R5
R4	3	3	3	A=1 | B=2 | C=3	R1 R2 R3 R4 R5
R5	3	2	3	A=1 & B=2 & C=3	R1

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

1. скобки
2. ¬ — инверсия — логическое отрицание
3. & — конъюнкция — логическое умножение
4. | — дизъюнкция — логическое сложение
5. → — импликация — логическое следование
6. ↔ — эквивалентность – логическое равенство

Пример 1. Вычислим истинность сложного высказывания:

не 2×2=5 и 2×2=4 или 3×3=8 и 3×3=9

Решение:

1. Выделим простые высказывания с помощью переменных A, B, C и D:
   А = 2×2=5 значение -ложь (0);
   В = 2×2=4 значение -истина (1);
   C = 3×3=8 значение -ложь (0);
   D = 3×3=9 значение -истина (1)
2. Тогда составное высказывание перепишем в следующей форме:
   не A и B или C и D
3. заменим в составном высказывании значения логических переменных:
   не 0 и 1 или 0 и 1
4. Подставим логические операции, получим логическое выражение:
   ¬0 × 1 V 0 × 1
5. Запишем по действиям, учитывая последовательность выполнения операций:
   1. ¬0 = 1
   2. 1 × 1=1
   3. 0 × 1 = 0
   4. 1 V 0 = 1

Ответ: не 2×2=5 и 2×2=4 или 3×3=8 и 3×3=9 = 1

Пример 2: Для какого имени истинно логическое условие:

¬ (Первая буква согласная → Третья буква гласная)

1. Юлия 2. Пётр 3. Алексей 4. Ксения.

Решение: По условию нужно получить истину(1), а отрицание ¬ (…) логическому условию вынуждает нас найти в скобках ложь НЕ(ЛОЖЬ)=ИСТИНА. Т.к. в условии операция импликация, а в ней ложь только в одном случае, когда из истиной предпосылки следует ложный вывод, т.е. нужно найти первую букву действительно согласную, а третью НЕгласную(т.е. согласную).

Ответ: Пётр.

Пример 3: Какое из названий имён удовлетворяет условию:

первая буква гласная & последняя буква гласная ↔ имя содержит букву «о»?

1. Иван 2. Алёна 3. Игорь 4. Ирина.

Решение: По условию нужно получить истину. Операция & имеет приоритет выше чем ↔, значит последовательность решения такая:

1. первая буква гласная & последняя буква гласная
2. Результат 1-го пункта ↔ название содержит букву «о»

Финальное решение примера это пункт 2 содержащий истину операции ↔.
Это либо 1↔1, либо 0↔0. Истинность 1-го пункта – имя под номером 2 или 4. Истинность 2-го пункта это имя 3 с буквой «о» что не верно.
Значит, ищем ложность обоих пунктов: ложность 1-го пункта – имя под номером 1 или 3. Ложность 2-го пункта это либо имя 1 буквы «о»,
либо имя 3 без буквы «о».

Ответ: Иван.

Пример 4: Какое из названий имён удовлетворяет условию:

первая буква гласная & последняя буква гласная ↔ ¬название содержит букву «а»?

1. Иван 2. Алёна 3. Игорь 4. Ирина.

Решение: По условию нужно получить истину. Операция & имеет приоритет выше чем ↔, а операция ¬
имеет приоритет выше чем &, значит последовательность решения такая:

1. ¬ название содержит букву «а»
2. первая буква гласная & последняя буква гласная
3. Результат 2-го пункта ↔ результат 1-го пункта

Финальное решение примера — это пункт 3 содержащий истину операции ↔. Это либо 1↔1, либо 0↔0. Истинность 1-го пункта – имя под номером 3. истинность 2-го пункта – имя под номером 2 и 4. Истинность 3-го пункта не может быть из-за неравенства 1-го и 2-го пункта. Значит для истинности 3-го пункта, ищем ложность 1-го и 2-го пунктов: ложность 1-го пункта – имя под номером 1, 2 или 4 или 4. Ложность 2-го пункта это либо имя 1, либо имя 3.

Ответ: 1.

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

Пример. Постройте ТИ для сложного высказывания ¬А & В | A & B

Решение:

1. Определим количество строк в ТИ, оно равно количеству возможных комбинаций логических переменных. Если количество переменных n, то количество строк = 2ⁿ. У нас переменные это А и В значит количество строк 4
2. Определим количество столбцов в ТИ, оно равно количеству переменных плюс количество логических операций. В нашем случае переменных две, а операций четыре(¬, &, | и &), т.е. количество столбцов равно шести.
3. Построим ТИ с указанным количеством строк и столбцов плюс одна строка сверху с обозначениями столбцов и внесём в таблицу исходные значения логических переменных.
4. Заполним ТИ, выполняя логические операции в необходимом порядке.

A	B	¬A	¬A & B	A & B	¬A & B | A & B
0	0	1	0	0	0
1	0	0	0	0	0
0	1	1	1	0	1
1	1	0	0	1	1

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

Пример. Докажем, что выражения A Λ B и (А V B) равносильны.

Решение:

1. Построим сначала ТИ логического выражения A Λ B:

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

2. Теперь построим ТИ логического выражения (А V B):

A	B	(A V B)	(А V B)
0	0	0	1
1	0	1	0
0	1	1	0
1	1	1	0

Значения последних столбцов ТИ совпадают, соответственно логические выражения
A Λ B и (А V B) равносильны

Пример. Докажите с помощью ТИ, что операция импликации A → B равносильна логическому выражению A V B

Пример. Докажите с помощью ТИ, что операция эквивалентности A ↔ B равносильна логическому выражению (A V B ) Λ ( A V B )

Пример. Дан фрагмент таблицы истинности выражения F.

X	Y	Z	F
0	0	0	1
0	0	1	0
0	1	0	1

Какое выражение соответствует F?

1. ¬X & ¬Y & Z
2. ¬X | ¬Y | Z
3. X | Y | ¬Z
4. X | Y | Z

Решение:

¬X & ¬Y & Z	¬X | ¬Y | Z	X | Y | ¬Z	X | Y | Z
¬0 & ¬0 & 0 = 0	¬0 | ¬0 | 0 = 1	0 | 0 | ¬0 = 1	X | Y | Z =
¬0 & ¬0 & 1 =	¬0 | ¬0 | 1 = 1	0 | 0 | ¬1 = 0	X | Y | Z =
¬0 & ¬1 & 0 =	¬0 | ¬1 | 0 =	0 | 1 | ¬0 = 1	X | Y | Z =

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

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

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

Ответ: 3