Логические основы ЭВМ

1.

1.Алгебра
высказываний
4. Логические
операции
2.Логические
переменные
5. Виды логических
операций
3.Логические
функции
6. Таблица
истинности функций

2.

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

3.

Алгебра высказываний
Алгебра высказываний была
разработана для того, чтобы
определять истинность или
ложность составных
высказываний, не вникая в
их содержание

4.

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

5.

Логические
переменные
Логические переменные– простые
высказывания, содержащие только
одну мысль.
Обозначаются буквами латинского
алфавита:
A, B, C…
Логические переменные могут
принимать лишь два значения:
«ИСТИНА» (1) или «ЛОЖЬ» (0)

6. СПОСОБЫ ЗАПИСИ ЗНАЧЕНИЙ ЛОГИЧЕСКИХ ВЫРАЖЕНИЙ

Истина
Ложь
И
Л
True T
False F
1
0

7.

Например, два простых
высказывания:
А=
«2 2 = 4» истина (1)
В = «2 2 = 5»
ложь (0)
являются логическими
переменными
А
и
В

8.

В алгебре высказываний
высказывания
обозначаются именами
логических переменных,
которые могут принимать
лишь два значения:
«ИСТИНА» (1) или
«ЛОЖЬ» (0)

9.

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

10.

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

11.

Каждое составное высказывание можно
выразить в виде формулы (логического
выражения), в которую входят логические
переменные, обозначающие высказывания, и
знаки логических операций, обозначающие
логические функции.
Для записи составного высказывания в виде
логического выражения на формальном языке
в составном высказывании нужно выделить
простые высказывания и логические связи
между ними.
запишем в форме логического выражения
составное высказывание "(2*2=5 или 2*2=4) и
(2*2 5 или 2*2 4)".Проанализируем составное
высказывание. Оно содержит два простых
высказывания:
А= "2*2=5" - ложно (0)
В= "2*2=4" - истинно (1)
Тогда составное высказывание можно записать
в следующей форме: "(А или В) и ( А или В)".

12.

ЛОГИЧЕСКАЯ ОПЕРАЦИЯ
способ построения сложного
высказывания из данных
высказываний, при котором значение
истинности сложного высказывания
полностью определяется значениями
истинности исходных высказываний.
Инверсия
Конъюнкция
Дизъюнкция
Импликация
Эквиваленция

13.

Объединение двух или
нескольких
высказываний в одно с
помощью союза «И»
называется операцией
логического
умножения, или
конъюнкцией

14.

Запись конъюнкции на формальном
языке алгебры высказываний
F(A,B) = A & B
или
F(A,B) = A B
Также может встретиться запись,
типа:
F(A,B) = A * B
или
F(A,B) = A and B

15.

F(A,B) = A B
Логическая функция,
полученная в результате
конъюнкции, истинна
тогда и только тогда,
когда истинны все
входящие в него
логические переменные

16.

Конъюнкция. Определите
истинность логической функции
1) «2
2) «2
3) «2
4) «2
2
2
2
2
=
=
=
=
5»
5»
4»
4»
И
И
И
И
«3
«3
«3
«3
3
3
3
3
=
=
=
=
10»
9»
10»
9»
Истинна только функция (4)

17.

Значение логической
функции определяется
по ее таблице истинности
Таблица истинности
показывает какие
значения принимает
логическая функция
при всех возможных
значениях логических
переменных

18.

Таблица истинности
для конъюнкции
A
B
2 2 = 5 3 3 = 10
2 2=5
3 3=9
2 2 = 4 3 3 = 10
2 2=4 3 3=9
A B
ЛОЖЬ
ЛОЖЬ
ЛОЖЬ
ИСТИНА

19.

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

20.

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

21.

Запись дизъюнкции на
формальном языке
алгебры высказываний
F(A,B) = A B
Также может встретиться запись,
типа:
F(A,B) = A + B
или
F(A,B) = A or B

22.

F(A,B) = A B
Логическая функция,
полученная в результате
дизъюнкции, истинна
тогда, когда истинна хотя
бы одна из входящих в
него логических
переменных

23.

Дизъюнкция. Определите
истинность логической функции
1)
2)
3)
4)
«2
«2
«2
«2
2
2
2
2
=
=
=
=
5»
5»
4»
4»
ИЛИ
ИЛИ
ИЛИ
ИЛИ
«3
«3
«3
«3
Ложна только функция
(1), остальные истинны
3
3
3
3
=
=
=
=
10»
9»
10»
9»

24.

Таблица истинности
для дизъюнкции
A
B
2 2 = 5 3 3 = 10
2 2=5
3 3=9
A B
ЛОЖЬ
ИСТИНА
2 2 = 4 3 3 = 10
ИСТИНА
2 2=4
ИСТИНА
3 3=9

25.

Таблица истинности
для дизъюнкции
A
0
0
1
1
B
0
1
0
1
A B
0
1
1
1

26.

Присоединение частицы
«НЕ» к высказыванию
называется операцией
логического отрицания,
или инверсией

27.

Запись инверсии на формальном
языке алгебры высказываний
F(A) = ¬A
или
F(A) = Ā
Также может встретиться
запись, типа:
F(A) = not А

28.

F(A) = Ā
Логическое отрицание
(инверсия) делает
истинное высказывание
ложным, а ложное –
истинным
[логическая отрицательная
единица, перевертыш]

29.

Инверсия
Пусть
A = «2 2 = 4»
– истинное
высказывание, тогда
F(A) = «2 2 ≠ 4»
– ложное высказывание

30.

Таблица истинности
для инверсии
А
¬А
0
1
1
0

31.

Дополнительные
логические функции
Импликацию и эквивалентность можно
выразить через конъюнкцию, дизъюнкцию
и отрицание, поэтому их называют
дополнительными логическими функциями:
Импликация:
А → В = ¬A В или
А В = ¬A В или
А В = ¬A В
Эквивалентность:
А ↔ В = (¬A В) (¬B A) или
А В = (¬A В) (¬B A) или
А ≡ В = (¬A В) (¬B A)

32.

Объединение двух
высказываний, из которых
первое является условием, а
второе – следствием из него,
связанных между собой
словами «если…то»,
называется импликацией
(логическим следованием)

33.

Импликация ложна
тогда и только тогда,
когда
условие истинно,
а следствие ложно
Пример:
Если выучишь материал, то сдашь зачет
Это высказывание ложно только тогда, когда материал
выучен, а зачет не сдан, т.к. сдать зачет можно и
случайно, например если попался единственный знакомый
вопрос или удалось воспользоваться шпаргалкой

34.

Таблица истинности
для импликации
A
B
A→B
0
0
1
0
1
1
1
0
0
1
1
1

35.

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

36.

Таблица истинности
для эквивалентности
A
B
A B
0
0
1
0
1
0
1
0
0
1
1
1

37.

ПРИВЕДИТЕ ПРИМЕРЫ КОНЪЮНКЦИИ
Приведите примеры истинной и
ложной конъюнкции двух или
нескольких высказываний.
Приведите примеры истинной и
ложной дизъюнкции двух или
нескольких высказываний.
Как в русском языке может
обозначаться дизъюнкция?

38.

Найдите правильно построенное отрицание
суждения "Все воздушные шары зелёные":
Все воздушные шары не зелёные.
Не верно, что все воздушные шары зелёные.
Докажите свою точку зрения с помощью
определения. Запишите отрицания
следующих высказываний:
Сегодня хорошая погода.
Число 3 - чётное.
Некоторые млекопитающие не живут на суше.
Во всякой школе некоторые ученики
увлекаются программированием.

39. Запишите схематически следующие высказывания

Быть иль не быть - вот в чем
вопрос." (Шекспир)
А V Ā <=> В
"Если хочешь быть красивым,
поступи в гусары." (К. Прутков)А => В
Ядерная энергия - это не
электричество, не тяготение, просто
химия - словом, неизвестно что.
А <=> B v C < = > D v P
Если краткость - сестра таланта, то
сокращение - дитя гения. А => В

40.

Формула Высказывание
A
В
не A
не B
AиB
A или B
Зверь полосатый
Зверь хищный
Тигр Волк Бурундук Заяц Медведь