4_Основы логики(2) (2)

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

Логика – смирительная рубашка фантазии.
Х.Нар
Основы логики

2. ТЕМЫ

⚫ Формы мышления
⚫ Алгебра логики
⚫ Логические операции
⚫ Логические выражения
⚫ Таблицы истинности
⚫ Логические схемы
⚫ Логические законы
⚫ Правила преобразования логических
выражений
⚫ Решение логических задач

3. Формы мышления

Логика – это наука о формах и
способах мышления.
Основы логики были заложены работами
ученого и философа Аристотеля
(384 -322гг. до н.э.).
Он пытался первым найти ответ на вопрос: «Как мы
рассуждаем?», изучал правила мышления. Аристотель
впервые дал систематическое изложение логики.
Он подверг анализу человеческое мышление, его формы.
Так возникла формальная логика.
Мышление всегда существует в каких – то формах
– это понятие, высказывание, умозаключение.

4. Формы мышления

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

5. Формы мышления

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

6. Формы мышления

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

7.

Примеры умозаключений
Дано высказывание: «Все углы равнобедренного треугольника
равны». Получите путем умозаключений из предыдущего другое
высказывание: «Этот треугольник равносторонний».
Следовательно,
А=В=С. Треугольник
равносторонний.
Пусть основанием
треугольника
является сторона
С
а
в
с
Тогда В=С
Тогда А=В
Так как в треугольнике все углы
равны, следовательно,
основанием может быть любая
другая сторона, например, А.

8. Алгебра логики

Эпоха Возрождения - началась философия и математика
Рене
Декарта (1596-1650). Декарт рекомендовал науке о мышлении - логике руководствоваться общепринятыми в математике принципами.
Появления
математической,
или
символической,
логики.
Основоположником математической логики считают великого немецкого
математика и философа Готфрида Вильгельма Лейбница (1646-1716).
Он попытался построить первые логические исчисления: арифметические и
буквенно-алгебраические, что можно заменить простые рассуждения
действиями со знаками, и привел соответствующие правила.
Английский математик Джордж Буль (1815-1864) развил окончательно
идею, предложенную Лейбницем. Буль считается основоположником
математической логики как самостоятельной дисциплины. Он вывел для
логических построений особую алгебру (алгебру логики). В отличии от обычной,
в ней символами обозначаются не числа, а высказывания. Алгебру логики
иначе называют алгеброй высказываний. В математической логике суждения
называются высказываниями.
В 1938 году выдающийся американский математик и инженер Клод Элвон
Шеннон (1916-2001) обнаружил, что алгебра логики приложима к любым
переменным, которые могут принимать только два значения. Например, к
состоянию контактов: включено - выключено или напряжению (или току): есть нет, которыми представляется информация в ЭВМ.

9. Алгебра логики

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

10. Алгебра логики

Высказывание
Простое (логическая
переменная)
Сложное
(логическая функция)
содержит только одну простую
мысль. Логические
переменные обычно
обозначаются буквами
латинского алфавита: A, B, C ...
содержит несколько простых
мыслей, соединенных между
собой с помощью логических
операций
Пример:
A = {Квадрат — это ромб}.
Значением логической переменной
могут быть только константы
ИСТИНА (1) и ЛОЖЬ (0).
Пример:
F(A,B) = {Лил дождь, и дул ветер}.
A
B
Значения логической функции при
различных наборах входных
переменных обычно задают
специальной таблицей
истинности.

11. Логические операции

Логическая операция – способ построения сложного
высказывания из данных высказываний, при котором
значение истинности сложного высказывания полностью
определяется
значениями
истинности
исходных
высказываний.
БАЗОВЫЕ
⚫ Конъюнкция
⚫ Дизъюнкция
⚫ Инверсия
ДОПОЛНИТЕЛЬНЫЕ
Импликация
Эквивалентность

12. Конъюнкция – логическое умножение (операция И)

Обозначение: A & B, A ˄ B, А и В, A and B
Конъюнкция
двух
логических
переменных
истинна тогда и только
тогда, когда истинны обе
логические переменные.
Примеры: «Число 10 четное и
отрицательное.»
«Нижний Новгород расположен на
берегах реки Волга и реки Ока.»
Таблица истинности
A
0
0
1
1
B
0
1
0
1
A˄B
0
0
0
1
Логическую операцию И можно сравнить с последовательным соединением лампочек в
гирлянде. При наличии хотя бы одной неработающей лампочки электрическая цепь
оказывается разомкнутой, т. е. Гирлянда не работает. Ток протекает только при одном
условии — все составляющие сети должны быть исправны.

13. Дизъюнкция – логическое сложение (операция ИЛИ)

Обозначение: A v B, А или В, A or B
Дизъюнкция
двух
логических
переменных
ложна тогда и только
тогда, когда ложны обе
логические переменные.
Примеры: «Число 10 четное или
отрицательное.»
«Нижний Новгород расположен на
берегу реки Енисей или реки Лена.»
Таблица истинности
A
0
0
1
1
B
0
1
0
1
A˅B
0
1
1
1
Кто хоть однажды использовал елочную гирлянду с параллельным соединением
лампочек, знает, что гирлянда будет светить до тех пор , пока цела хотя бы одна
лампочка. Логическая операция ИЛИ чрезвычайно схожа с работой подобной гирлянды,
ведь результат операции ложь только в одном случае — когда все аргументы ложны.

14. Инверсия – отрицание (операция НЕ)

Обозначение: A, ¬A, не А, not A
Таблица истинности
Инверсия
логической
переменной ложна тогда и
только тогда, когда сама
логическая
переменная
истинна и наоборот.
А
¬А
0
1
1
0
Примеры: «Неверно, что число 10 — четное.»
«Неверно, что Нижний Новгород расположен
на берегу реки Енисей.»
Принцип работы переключателя настольной лампы таков: если лампа
горела, переключатель выключает ее, если лампа не горела — включает ее.
Такой переключатель можно считать электрическим аналогом операции
отрицания

15. Импликация – логическое следование (операция ЕСЛИ-ТО)

Обозначение: A → B, если А то В, А влечет В, if A then
B, где А – условие, В – следствие. Таблица истинности
Импликация
двух
логических
переменных
ложна тогда и только
тогда, когда из истинного
основания
(А)
следует
ложное следствие.
A
0
0
1
1
B
0
1
0
1
A→B
1
1
0
1
Примеры: «Если число 10 четное, то оно является отрицательным.»

16. Эквивалентность – логическое равенство (операция А тогда и только тогда, когда В)

Обозначение: A ≡ B, A
B
Эквивалентность
двух
логических
переменных
истинна тогда и только тогда,
когда
оба
высказывания
одновременно либо ложны,
либо истинны.
Таблица истинности
A
0
0
1
1
B
0
1
0
1
A
B
1
0
0
1
Примеры: «День сменяет ночь тогда и только тогда, когда солнце скрывается за
горизонт»

17. Логическое выражение

Если составное высказывание (логическую функцию)
выразить в виде формулы, в которую войдут логические
переменные и знаки логических операций, то получится
логическое выражение, значение которого можно вычислить.
Значение логического выражения - только ЛОЖЬ или ИСТИНА
При выполнение операций определен следующий порядок
их выполнения:
1) действия в скобках;
2) инверсия,
эквивалентность.
конъюнкция,
дизъюнкция,
Далее рассмотрим пример:
импликация,

18.

Логическое выражение
Пример:
Записать в виде логического выражения следующее высказывание:
«Летом Петя поедете в деревню и, если будет хорошая погода, то он
пойдет на рыбалку».
1. Проанализируем составное высказывание.
Оно состоит из трех простых высказываний, которые обозначим через
логические переменные:
А = Петя поедет в деревню;
В = Будет хорошая погода;
С = Он пойдет на рыбалку.
2. Запишем высказывание в виде логического выражения, учитывая
порядок действий, при необходимости расставляя скобки:
F = A˄(B→C)
Задание на закрепление:
1. Неверно, что 10>Y>5 и Z<0;
2. A является max(A,B,C);
3. Если X делится на 9, то X делится и на 3.

19.

Построение
таблицы истинности
Таблица истинности — таблица, в которой по действиям
показано, какие значения принимает логическое выражение при
всех возможных наборах его переменных.
Пример:
Построить таблицу истинности для логической функции F(A,B,C)= ¬C˄(AvB)
При построении таблицы истинности целесообразно руководствоваться
последовательностью действий:
1. Определить количество строк в
таблице, оно равно 2n+1, где n- количество
логических переменных.
2. Определить количество столбцов в
таблице истинности, оно равно количеству
логических переменных плюс количество
логических операций.
3.
Установить
последовательность
выполнения логических операций.
1. Количество строк = 23+1=9
2. Количество столбцов = 3+3 = 6
3. 1 действие ¬С,
2 действие AvB,
3 действие ¬C^(AvB)

20. Построение таблицы истинности

4. Построить таблицу с указанием
количества строк и столбцов, обозначить
столбцы и внести все возможные наборы
значений логических переменных:
4.1) разделить столбец значений первой
переменной пополам и заполнить
верхнюю часть колонки нулями, а
нижнюю – единицами;
4.2) разделить столбец значений второй
переменной на четыре части и заполнить
четверти чередующимися группами
нулей и единиц, начиная с группы нулей;
4.3) продолжить деления столбцов
значений последующих переменных на 8,
16 и т.д. частей и заполнять их группами
нулей и единиц, до тех пор пока группа
нулей (единиц) не будет состоять из
одного символа.
A
B
C
0
0
0
0
0
1
0
1
0
1
0
0
1
1
0
1
0
1
0
1
1
1
1
1
¬C
A˅B
F()

21.

Построение
таблицы истинности
5. Заполнить таблицу истинности по столбцам выполняя базовые логические
операции в соответствии с их таблицами истинности. F(A,B,C)= ¬C^(AvB)
A
B
C
¬C
A˅B
F(A,B,C)
0
0
0
1
0
0
0
0
1
0
0
0
0
1
0
1
1
1
1
0
0
1
1
1
1
1
0
1
1
1
1
0
1
0
1
0
0
1
1
0
1
0
1
1
1
0
1
0
Задание на закрепление: Постройте таблицу истинности
1. F = (AvB)^(¬Av¬B);
3. F=((Av¬B)→B)&(¬AvB)
2. F = XvY^¬Z;
4. F= ¬(A^B) (¬AvB)

22. Логические схемы

Базовые логические элементы реализуют
три основные логические операции:
⚫ Логический элемент «И» - конъюнктор.
⚫ Логический элемент «ИЛИ»- дизъюнктор.
⚫ Логический элемент «НЕ»-инвертор.
Логические элементы оперируют с сигналами,
импульсами. Есть импульс - логический смысл
сигнала - 1, нет импульса – 0. На входы поступают
сигналы – значения аргументов, на выходе
появляется сигнал – значение функции.

23. Логический элемент «И»

A
F=A^B
Логический элемент «ИЛИ»
B
A
B
Логический элемент «НЕ»
A
F=¬A
1
F=AvB

24.

Так как сигнал, выработанный одним логическим элементом,
можно подавать на вход другого, то эта дает возможность
образовывать цепочки из отдельных логических элементов.
Каждую такую цепочку будем называть схемой логического
устройства.
Правила построения логических схем:
1) определить число логических переменных;
2) определить количество базовых логических операций
и их порядок;
3) изобразить для каждой логической операции
соответствующий ей элемент;
4) составить
элементы
в
порядке
выполнения
логических операций.

25.

Задание 1:
1. Построить логическую схему по логической
функции: F = (⌐A & ⌐B)&(CvD)
Решение:
У нас в формуле имеется 4 логических переменных A,B,C,D. С
помощью них составлено 5 базовых логических операций. Порядок
выполнения операций будет следующий:
1)
2)
3)
4)
5)
⌐А- логический элемент «НЕ»
⌐В - логический элемент «НЕ»
(⌐А& ⌐В) - логический элемент «И»
(CvD) - логический элемент «ИЛИ»
(⌐A & ⌐B)&(CvD) - логический элемент «И»

26.

Логическая схема:
А
B
C
D
Задание на закрепление: Постройте логическую схему
1. F = AvB&¬C;
2. F = ¬AvB&C;
3. F = B&¬Av¬B&A.
4. F= ¬(A&B&C)

27.

Задание 2.
Построить логическое выражение по логической
схеме:
&
̚
&
1
Обозначим входные сигналы А и В, эти сигналы одновременно
поступают на логические элементы "И" и "ИЛИ", но учитывая
иерархию выполнения операций сначала выполним:
1) A&B
2) AvВ
3) ⌐(А&В)
4) (AvB)& ⌐(А&В)
Ответ: логическая формула F=(AvB)& ⌐(A&B).

28. Законы логики

F(A)=AvA
«Этот треугольник прямоугольный или
косоугольный»
Логические функции, истинные на всех наборах значений
входных переменных, называются тождественно-истинными.
F(A)=A&A
«Катя самая высокая девочка в классе, и
в классе есть девочки выше Кати»
Логические функции, ложные на всех наборах значений
входных переменных, называются тождественно-ложными.

29. Законы логики

X
&
Y
v
X
&
Y
&
Z
v
X
&
Z
&
P=
(YvZ&P)
X&
Логические функции называются равносильными, если их
истинностные значения совпадают при любых значениях,
входящих в них логических переменных.
Формула имеет нормальную форму, если в ней отсутствуют
знаки эквивалентности, импликации двойного отрицания, при
этом знаки отрицания находятся только при логических
переменных.

30. Законы логики

31. Преобразование логического выражения

Упростить логическое выражение
(A
)→
(B
)
F
=
v
B
v
C
1. Избавимся от импликации и отрицания.
(
)(
)
(
)(
)
A
v
B
→
B
v
C
=
A
vB
&
B
v
C
2. Применим закон двойного отрицания.
(
)(
)(
)(
)
A
vB
&
B
v
C
=
A
vB
&
B
v
C
3. Применим закон дистрибутивности.
(
)
(
)
(
)
(
)
A
vB
&
B
v
C
=
A
v
B
&
B
v
A
v
B
&
C

32.

Преобразование логического
выражения
4. Применим закон коммутативности и закон дистрибутивности.
(
)
(
)
A
v
B
&
B
v
A
v
B
&
C
=
A
&
B
v
B
&
B
v
A
&
C
v
B
&
C
5. Применим закон идемпотенции.
A
&
B
v
B
&
B
v
A
&
C
v
B
&
C
=
A
&
B
v
B
v
A
&
C
v
B
&
C
6. Применим закон дистрибутивности, вынесем за скобки В.
()
A
&
B
v
B
v
A
&
C
v
B
&
C
=
B
&
A
v
1
v
A
&
C
v
B
&
C

33. Преобразование логического выражения

7. Применим правило операции с константой.
(
)
B
&
A
v
1
v
A
&
C
v
B
&
C
=
B
v
A
&
C
v
B
&
C
8. Применим переместительный закон и вынесем В за скобки
используя дистрибутивный закон.
(
)
B
v
A
&
C
v
B
&
C
=
B
&
1
v
C
v
A
&
C
9. Применим правило операции с константой.
(
)
B
&
1
v
C
v
A
&
C
=
B
v
A
&
C
Ответ: F
(
)
(
)
=
A
v
B
→
B
v
C
=
B
v
A
&
C

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

Задача №1
Маша, Саша и Миша во время летней практики нашли старинную амфору и показали
учителю истории. Он попросил высказать каждого из них предположение о том, что
это за амфора. Ребята сказали:
Маша: «Эта амфора греческая и изготовлена в 5 веке»;
Саша: «Эта амфора финикийская и изготовлена в 3 веке»;
Миша: «Эта амфора не греческая и изготовлена в 4 веке».
Каждый из ребят оказался прав только в одном предположении. Где и в каком веке была
изготовлена амфора.
Решение
1. А – «Греческая амфора»
В – «Изготовлена в V веке»
С – «Изготовлена в III веке»
D – «Изготовлена IV в веке»
2. Маша: «Греческая и изготовлена в V веке»
A&
BvA&
B
Саша: «Не греческая и изготовлена в III веке»
A&
CvA
&
C
Миша: «Не греческая и изготовлена в IV веке»
A&
D
vA
&
D

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

(
)
(
)(
)
3. A
&
B
v
A
&
B
&
A
&
C
v
A
&
C
&
A
&
D
v
A
&
D
=
1
1 способ – решение задачи путем построения таблицы истинности
Таблица истинности
Ответ: это финикийская амфора, которая была
изготовлена в v веке.

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

(
)
(
)(
)
3. A
&
B
v
A
&
B
&
A
&
C
v
A
&
C
&
A
&
D
v
A
&
D
=
1
2 способ – решение задачи путем упрощения логического
выражения
)
)
(
)
(
(
A
&
B
v
A
&
B
&
A
&
C
v
A
&
C
&
A
&
D
v
A
&
D
=
(
)
=
A
&
B
&
A
&
C
v
A
&
B
&
A
&
C
v
A
&
B
&
A
&
C
v
A
&
B
&
A
&
C
(
)
(
)
(
)
&
A
&
D
v
A
&
D
=
A
&
B
&
C
v
A
&
B
&
C
&
A
&
D
v
A
&
D
=
=
A
&
B
&
C
&
A
&
D
v
A
&
B
&
C
&
A
&
D
vA
&
B
&
C
&
A
&
D
v
v
A
&
B
&
C
&
A
&
D
=
A
&
B
&
C
&
D
v
A
&
B
&
C
&
D
Ответ: это финикийская амфора, которая была изготовлена в v
веке.

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

Этапы решения логических задач
1. Изучить условие задачи.
1. Ввести логические переменные для обозначения простых высказываний.
1. Формализовать условие задачи с помощью языка алгебры логики.
1. Составить конечную логическую формулу, описывающую все логические
связи сформулированные условием задачи, прировнять к 1.
1. Упростить формулу и/или построить таблицу истинности.
1. Проанализировать условие задачи.
1. Записать ответ.