1.87M

Category:

informatics

АЛГЕБРА ЛОГИКИ

1. АЛГЕБРА ЛОГИКИ

2. ИСТОРИЯ РАЗВИТИЯ АЛГЕБРЫ ЛОГИКИ

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

3. Этапы развития логики:

I этап – формальная логика.
Основатель – древнегреческий философ Аристотель
(384-322 гг. до н.э.), первым систематизировал формы и
правила мышления, сформулировал основные законы мышления,
ввел основные формы абстрактного мышления, разработал теорию
умозаключений и доказательств.
Античную логику, основанную Аристотелем, принято называть
формальной логикой.
Формальная логика связана с анализом
обычных рассуждений, выражаемых разговорным
языком.

4.

II этап – математическая логика
Основатель – немецкий ученый философ и математик
Г.В.Лейбниц (1646-1716), высказал идею о возможности
математизации логики.
Он пытался создать универсальный язык, с помощью которого
разрешались бы споры между людьми, каждому понятию и суждению можно
было бы дать числовую характеристику и установить такие правила
оперирования с этими числами, которые позволили бы сразу определить,
истинно данное суждение или ложно.
Будущую теорию (которую он так и не завершил) он называет «всеобщая
характеристика». Она включала все логические операции, свойства которых
он ясно представлял
Математическая
логика
рассуждений с помощью символов.
–
запись

5.

III этап – математическая логика (булева алгебра).
Основатель – английский математик Джордж
Буль (1815-1864), перенес на логику законы и
правила алгебраических действий, ввел логические
операции, предложил
символической форме.
способ
записи
высказываний
в
Алгебра
логики
(математическая
логика)
оперирует
с
двоичными
переменными, принимающими только
два значения – «истина» или «ложь».
Клод Шеннон (1916-2001). Его
позволили
применить
алгебру
вычислительной технике
исследования
логики
в

6. Основные формы мышления

Мышление всегда существует в каких-то формах.
Основными формами мышления являются:
• понятие
• высказывание
• умозаключение

7.

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

8.

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

9.

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

10.

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

11.

Примеры высказываний:
Земля – планета Солнечной системы (истинное высказывание).
• 3 + 6 > 10 (ложное высказывание).
• Площадь прямоугольного треугольника равна произведению катетов (ложное
высказывание).
• Площадь прямоугольного треугольника равна половине произведения катетов
(истинное высказывание).
• Если на улице дождь, то асфальт – мокрый (истинное высказывание).
• Свободу и комфорт человеку дают деньги (истинное или ложное высказывание,
субъективно).
• Солнце светит для всех (истинное высказывание).
• Все ученики любят информатику (ложное высказывание).
• Некоторые ученики любят информатику (истинное высказывание)
• Ты любишь информатику? (не высказывание, т.к. предложение не повествовательное).
• Посмотри в окно (не высказывание).
• Х*Х<0 (ложное высказывание, т.к. х*х всегда неотрицательно).
• 2*Х -5>0 (не высказывание, так как результат зависит от Х, значение которого
неизвестно).

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

Алгебра логики (алгебра высказываний) – раздел
математической логики, изучающий строение сложных
логических высказываний и способы установления их
истинности с помощью алгебраических методов.
В алгебре логики простые высказывания заменяют
логическими
переменными,
которые
обозначаются
латинскими буквами, причем значениями переменных
могут быть только 0 (ложь) или 1 (истина).
Например:
A = Все мальчики – хулиганы. = 0 – ложное высказывание
B = В школе дети изучают информатику. = 1 – истинное высказывание

13.

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

14.

Логическая переменная – простое
высказывание, обозначенное буквой и
имеющее значение «ИСТИНА» (1) или
«ЛОЖЬ» (0)
Логическая функция (выражение) –
составное высказывание, состоящее из
логических переменных, связанных
логическими операциями
А = «У ромба диагонали в точке пересечения
делятся пополам» = «ИСТИНА»
В = «У ромба диагонали перпендикулярны» =
«ИСТИНА»
«У ромба диагонали перпендикулярны и
в точке пересечения делятся пополам»
F(A, B) = A и B
Логические операции – логические действия над логическими
переменными.

15.

Основные логические операции
1.
Конъюнкция (логическое умножение)
от лат. Conjunctio – связываю, соответствует союзу И.
Обозначение: ∩, ˄ &, and, И
Например:
На автостоянке стоят «Мерседес» и «Жигули»
Обозначим высказывания:
А = На автостоянке стоит «Мерседес».
В = На автостоянке стоят «Жигули».
Конъюнкция:
На автостоянке стоят «Мерседес» и «Жигули» = A ∩ B

16.

Конъюнкция двух высказываний истинна тогда и только тогда, когда оба
высказывания истинны, и ложна, когда хотя бы одно высказывание ложно.
Таблица истинности для конъюнкции
Пример: Даны высказывания:
A
B
A∩B
0
0
1
1
0
1
0
1
0
0
0
1
А – «Число 10 – четное» = ИСТИНА =1
В – «Число 10 – отрицательное» = ЛОЖЬ = 0
С – «Число 10 кратно 2» = ИСТИНА = 1
A ∩ B – «Число 10 – четное и отрицательное» - ЛОЖЬ = 1 ∩ 0 = 0
A ∩ С – «Число 10 четное и кратное 2» - ИСТИНА = 1 ∩ 1 = 1
Графическое представление конъюнкции
A
А&В
B

17.

Дизъюнкция (логическое сложение)
Это логическое ИЛИ, т.е это когда мы говорим, что верно либо одно
утверждение, либо другое или оба сразу
Обозначение:
U ,˅, |, + , или, or.
Например:
На автостоянке стоят «Мерседес» или «Жигули».
Обозначим высказывания:
А=На автостоянке стоит «Мерседес».
В=На автостоянке стоят «Жигули».
Дизъюнкция:
На автостоянке стоят «Мерседес» или «Жигули» = A U B

18.

Пример:
•Утверждение A: «Сегодня солнечно».
•Утверждение B: «Сегодня идёт дождь».
Дизъюнкция A ∨ B (A ИЛИ B) означает, что верно хотя бы одно из этих
утверждений: либо сегодня солнечно, либо сегодня идёт дождь (или оба
варианта одновременно).
Важно: если хотя бы одно из утверждений истинно, то дизъюнкция считается
истинной.

19.

Дизъюнкция двух высказываний ложна тогда и только тогда, когда оба высказывания
ложны, и истинна, если хотя бы одно высказывание истинно.
Таблица истинности для конъюнкции
Пример: Даны высказывания
A
0
0
1
1
B
0
1
0
1
AUB
0
1
1
1
А – «Число 10 – четное» = ИСТИНА = 1
В – «Число 10 – отрицательное» = ЛОЖЬ = 0
С – «Число 10 - простое» = ЛОЖЬ = 0
А U В – «Число 10 – четное или отрицательное» - ИСТИНА = 1 U 0 = 1
А U С – «Число 10 четное или простое» - ИСТИНА = 1 U 0 = 1
В U С – «Число 10 отрицательное или простое» - ЛОЖЬ = 0 U 0 = 0
Графическое представление дизъюнкции
A
B
АVВ

20.

Инверсия (отрицание)
от лат. Inversio – переворачиваю. Логическое отрицание образуется
из высказывания с помощью добавления частицы «не» к сказуемому
или использования оборота речи «неверно, что …».
Обозначение: Ā, ¬A, ⌉A, не A.
Например:
Обозначим высказывание:
A = Я люблю информатику.
Инверсия:
Я не люблю информатику = ¬A
Неверно, что я люблю информатику = ¬A

21.

Инверсия высказывания истинна, когда высказывание ложно и наоборот, ложна,
когда высказывание истинно.
Таблица истинности для инверсии
Пример: Даны высказывания
A
¬A
0
1
1
А – «Число 10 – четное» = ИСТИНА = 1
В – «Число 10 – отрицательное» = ЛОЖЬ = 0
С – «Луна – спутник Земли» = ИСТИНА = 1
Не А – «Неверно, что число 10 – четное» = ЛОЖЬ = 0
Не В – «Число 10 – неотрицательное» = ИСТИНА = 1
Не С – «Луна – не является спутником Земли» = ЛОЖЬ
0
=0
Графическое представление инверсии
Ā
A

22.

Импликация (логическое следование)
соответствует речевому обороту ЕСЛИ A, ТО B; В, ЕСЛИ А; КОГДА А, ТОГДА В
Обозначение: →
Например:
Если на улице дождь, то асфальт мокрый .
Обозначим высказывания
А=На улице дождь.
В=Асфальт мокрый.
Импликация:
Если на улице дождь, то асфальт мокрый = A → B

23.

Импликация истинна всегда, за исключением случая, когда A истинно, а B ложно.
Импликация двух высказываний ложна тогда и только тогда, когда из истинного высказывания
следует ложное.
Импликация может быть представлена в виде:
Таблица истинности для импликации
A
0
0
1
1
B
0
1
0
1
A→B
1
1
0
1
А – «Число 10 – четное» = ИСТИНА = 1
В – «Число 10 – отрицательное» = ЛОЖЬ = 0
С – «Число 10 - простое» = ЛОЖЬ = 0
А → В – «Если число 10 – четное, то оно - отрицательное» =
ЛОЖЬ = 1 → 0 = 0
А → С – «Число 10 простое, если четное» = ЛОЖЬ = 1 → 0
=0

24.

Эквивалентность (равнозначность)
соответствует речевым оборотам ЭКВИВАЛЕНТНО; ТОГДА И
ТОЛЬКО ТОГДА, КОГДА.
Обозначение:
,=
Например:
Число кратно 3 тогда и только тогда, когда сумма его цифр делится нацело на 3
Обозначим высказывания:
А = Число делится на 3 без остатка.
В = Сумма цифр числа делится нацело на 3.
Эквивалентность:Число кратно 3 тогда и только тогда, когда сумма его цифр
делится нацело на 3 = A B

25.

Эквивалентность истинна тогда и только тогда, когда оба высказывания
истинны или ложны.
Таблица истинности для эквивалентности
Пример: Даны высказывания
А – «Число 10 – четное» = ИСТИНА = 1
В – «Число 10 – отрицательное» = ЛОЖЬ = 0
A
B
A
B
С – «Число 10 - простое» = ЛОЖЬ = 0
А
В – «Число 10 – четное, тогда и только тогда, когда оно отрицательное» = ЛОЖЬ = = 1
0=0
0
0
1
В
С – «Число 10 такое же простое, как и отрицательное» =
0
1
0
ИСТИНА = 0
0=1
Эквивалентность может быть представлена в виде:
1
0
0
1
1
1
A B = AB + A B

26.

Как легко запомнить логические операции?
Конъюнкция(/\): Умножение. Истина
допускается только тогда, когда оба
выражения истины.
Дизъюнкция(\/): Сложение. Ложь допускается
только тогда, когда оба выражения ложны.
Отрицание(¬): Обратная замена. Ложь на
истину, истина на ложь.
Импликация(→): Ложь допускается только
тогда, когда первое выражение истинно, а
второе ложно(1→0).

27.

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

28.

29.

Порядок составления таблиц истинности для логических
функций (логических выражений)
1. Определить количество строк в таблице истинности.
Количество строк = 2n, где n – количество логических переменных.
2.Определить количество столбцов в таблице истинности, равное количеству
логических переменных плюс количество логических операций.
3. Построить таблицу истинности с указанным количеством строк и
столбцов.
4. Ввести названия столбцов таблицы в соответствии с последовательностью
выполнения логических операций с учетом скобок и приоритетов.
5. Заполнить столбцы входных переменных наборами значений.
6. Заполнить таблицу истинности по столбцам, выполняя логические
операции в соответствии с установленной последовательностью.

30.

Пример 1
Построить таблицу истинности для логического выражения a a b
В данном выражении 2 логические переменные (a, b), 2 логические
операции, причем сначала выполняется конъюнкция, а затем дизъюнкция.
1.Количество строк в таблице истинности 2n = 22 = 4 (+ 1 строка для
«шапки»).
2.Количество столбцов – 4 (2 переменные + 2 логические операции)
3.Построить таблицу. Ввести названия столбцов. Учесть порядок
выполнения логических операций.