2. Тема: логические основы эвм

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

Высказывание (суждение) – некоторое предложение, которое может быть истинно (верно) или ложно.

Утверждение – суждение, которое требуется доказать или опровергнуть.

Рассуждение – цепочка высказываний или утверждений, определенным образом связанных друг с другом.

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

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

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

Логические операции и таблицы истинности.

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

F = A & B.

Логическое умножение КОНЪЮНКЦИЯ - это новое сложное выражение будет истинным только тогда, когда истинны оба исходных простых выражения. Конъюнкция определяет соединение двух логических выражений с помощью союза И.

F

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

= A+ B

Логическое сложение – ДИЗЪЮНКЦИЯ - это новое сложное выражение будет истинным тогда и только тогда, когда истинно хотя бы одно из исходных (простых) выражений. Дизъюнкция определяет соединение двух логических выражений с помощью союза ИЛИ.

Л

A	неА
1	1
1	0

огическое отрицание: ИНВЕРСИЯ -если исходное выражение истинно, то результат отрицания будет ложным, и наоборот, если исходное выражение ложно, то результат отрицания будет истинным. Данная операция означает, что к исходному логическому выражению добавляется частица НЕ или слова НЕВЕРНО, ЧТО….

Л

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

огическое следование: ИМПЛИКАЦИЯ - связывает два простых логических выражения, из которых первое является условием (А), а второе (В)– следствием из этого условия. Результатом ИМПЛИКАЦИИ является ЛОЖЬ только тогда, когда условие А истинно, а следствие В ложно. Обозначается символом "следовательно" и выражается словами ЕСЛИ … , ТО …

Л

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

огическая равнозначность: ЭКВИВАЛЕНТНОСТЬ - определяет результат сравнения двух простых логических выражений А и В. Результатом ЭКВИВАЛЕНТНОСТИ является новое логическое выражение, которое будет истинным тогда и только тогда, когда оба исходных выражения одновременно истинны или ложны. Обозначается символом "эквивалентности".

Порядок выполнения логических операций в сложном логическом выражении:

1. инверсия; 2. Конъюнкция; 3. Дизъюнкция; 4. Импликация; 5. эквивалентность

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

Построение таблиц истинности для сложных выражений:

Количество строк = 2ⁿ + две строки для заголовка (n - количество простых высказываний)

Количество столбцов = количество переменных + количество логических операций

При построении таблицы надо учитывать все возможные сочетания логических значений 0 и 1 исходных выражений. Затем – определить порядок действий и составить таблицу с учетом таблиц истинности основных логических операций.

Базовые логические элементы компьютера:

Логический элементИ

конъюнктор

Логический элемент ИЛИ

дизъюнктор

Логический элемент НЕ

инвертор

Построение таблиц истинности для сложных высказываний

Приоритет логических операций:

1) инверсия 2) конъюнкция 3) дизъюнкция 4) импликация и эквивалентность

Как составить таблицу истинности?

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

Для формулы, которая содержит две переменные, таких наборов значений переменных всего четыре: (0, 0), (0, 1), (1, 0), (1, 1).

Если формула содержит три переменные, то возможных наборов значений переменных восемь (0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1). Количество наборов для формулы с четырьмя переменными равно шестнадцати и т.д.

Удобной формой записи при нахождении значений формулы является таблица, содержащая кроме значений переменных и значений формулы также и значения промежуточных формул.

Контрольные вопросы:

1. Что такое логика?

2. Дайте определение умозаключению?

3. Дайте определение логическому выражению?

4. Какие законы логики Вы знаете?

5. Назовите основные логические операции.

6. Назовите базовые логические элементы компьютера.

ОСНОВНЫЕ ЗАКОНЫ АЛГЕБРЫ ЛОГИКИ

Закон	Для дизъюнкции	Для конъюнкции
1. Ассоциативность	Независимость от порядка выполнения однотипных действий
2. Коммутативность	Независимость от перестановки
3. Дистрибутивность (распределение)	Правила раскрытия скобок и вынесение
4. Идемпотентность	Отсутствие степеней и коэффициентов
5. Инволюция	Двойная инверсия
	=
6. Действия с абсолютно-истинными высказываниями
7. Действия с абсолютно-ложными высказываниями
8. Законы де Моргана	Отрицание одновременной истинности	Отрицание вариантов
9. Закон исключенного третьего и закон противоречия
10. Поглощение
11. Поглощение отрицания