Презентация на тему Логические основы компьютеров

с помощью 0 и 1.
Задача – разработать оптимальные правила

обработки таких данных.
Джордж Буль разработал основы алгебры, в которой используются только 0 и 1 (алгебра логики, булева алгебра).
Почему «логика»? Результат выполнения операции можно представить как истинность (1) или ложность (0) некоторого высказывания.

которого можно однозначно сказать, истинно оно или ложно.
Высказывание или

нет?
Сейчас идет дождь.
Жирафы летят на север.
История – интересный предмет.
У квадрата – 10 сторон и все разные.
Красиво!
В городе N живут 2 миллиона человек.
Который час?

открыта.
простые высказывания (элементарные)
Составные высказывания строятся из простых с помощью

логических связок (операций) «и», «или», «не», «если … то», «тогда и только тогда» и др.

A и B
A или не B
если A, то B
не A и B
A тогда и только
тогда, когда B

Сейчас идет дождь и открыта форточка.
Сейчас идет дождь или форточка закрыта.
Если сейчас идет дождь, то форточка открыта.
Сейчас нет дождя и форточка открыта.
Дождь идет тогда и только тогда, когда открыта форточка.

«Сегодня светит солнце»
В – «Сегодня идет дождь»
Логическое умножение (конъюнкция)

образуется соединением двух (или более) высказываний в одно с помощью союза «и».

языке: и.
А ^ B,– «Сегодня светит солнце и идет

дождь»

0

0

0

1

Таблица истинности

Конъюнкция двух высказываний истинна тогда и только тогда, когда оба высказывания истинны, и ложна, когда хотя бы одно из высказываний ложно.

Ложь

Ложь

Ложь

Истина

А И В; АВ; А&B; A AND B; A·B

На стоянке находится «Мерседес»
В – На стоянке находится «Жигули»
Логическое

сложение (дизъюнкция) образуется соединением двух (или более) высказываний в одно с помощью союза «или».

или.
А V B – На стоянке находится «Мерседес»

или «Жигули»

Дизъюнкция двух высказываний ложна тогда и только тогда, когда оба высказывания ложны, и истинна, когда хотя бы одно из высказываний истинно.

1

1

0

1

Истина

Истина

Ложь

Истина

Таблица истинности

А ИЛИ В; АВ; АB; A OR B; А+В

не светит солнце»
Логическое отрицание (инверсия) образуется из высказывания с

помощью добавления частицы «не» к сказуемому или использования оборота речи «неверно, что…».

А – «У данного компьютера жидкокристаллический монитор»

В – «Неверно, что у данного компьютера жидкокристаллический монитор»

неверно, что…
А – «Сегодня светит солнце»
¬ А –

«Неверно, что сегодня светит солнце» или «Сегодня не светит солнце»

1

0

Инверсия высказывания истинна, если высказывание ложно, и ложна, когда высказывание истинно.

Таблица истинности

на улице, то асфальт мокрый.

Если хорошо горит красный свет

на светофоре, то стою и жду зеленый.

Если прямо пойдешь, то коня потеряешь.

Если коровы летают, то дважды два – пять.

Логическое следование (импликация) образуется соединением двух высказываний в одно с помощью оборота речи «если…, то…».

тогда, когда из истинного высказывания следует ложное.
Истина

Ложь

Истина

Истина
ЛОГИЧЕСКОЕ СЛЕДОВАНИЕ (ИМПЛИКАЦИЯ)
А

– «На улице дождь»
В – «Асфальт мокрый»

А → B АB= ¬ А V В = «Если на улице дождь, то асфальт мокрый»

Таблица истинности

и только тогда, когда….


Число А – четное, тогда и

только тогда, когда число А делится нацело на 2.


Прямоугольник является квадратом тогда и только тогда, когда все его стороны равны.

ЛОГИЧЕСКОЕ РАВЕНСТВО

Логическое равенство (эквивалентность) образуется соединением двух высказываний в одно при помощи оборота речи «… тогда и только тогда, когда…».

– «Число А кратно 2»

А ↔ B – «Число

А – четное, тогда и только тогда, когда число А кратно 2»

0

0

1

1

Эквивалентность двух высказываний истинна тогда и только тогда, когда оба высказывания истинны или оба ложны.

Ложь

Ложь

Истина

Истина

Таблица истинности

их выражения через И, ИЛИ и НЕ:




Шаг 2. Раскрыть

инверсию сложных выражений по формулам де Моргана:

Шаг 3. Используя законы логики, упрощать выражение, стараясь применять закон исключения третьего.

¬ (A  B) = ¬ A  ¬ B

¬ (A  B) = ¬ A  ¬ B

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

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

Порядок вычисления:

- инверсия

- конъюнкция

- дизъюнкция

- импликация

- эквивалентность

 ¬(¬B  C).
1) ¬A  ¬B 

¬C 2) A  ¬B  ¬C 3) A  B  ¬C 4) A  ¬B  C
Решение (использование законов де Моргана):
перепишем заданное выражение и ответы в других обозначениях: заданное выражение
ответы: 1) 2) 3) 4)
посмотрев на заданное выражение, видим инверсию (операцию «НЕ») для сложного выражения в скобках, которую раскрываем по формуле де Моргана,

а затем используем закон двойного отрицания по которому :


или A  B  ¬C
таким образом, правильный ответ – 3 .

¬(A  ¬B) ¬(A  B) A  B

1)¬B  A 2)A  B  ¬B 3)A  B  ¬A 4)¬A

задания:

2. Какое логическое выражение эквивалентно выражению
A  ¬(¬B  ¬C)?
1)A  B  C 2)A  B  ¬C 3)A  (B  C) 4)(A  ¬B)  ¬C

3. Какое логическое выражение эквивалентно выражению
¬(A  B)  ¬C?
1)(A  B)  ¬C 2)(A  B)  C 3)(¬A  ¬B)  ¬C 4)(A  B)  C

4. Какое логическое выражение эквивалентно выражению
¬(A  ¬B)  ¬C?
1)A  B  C 2)¬(A  B)  C 3)¬(A  C)  B 4)¬(A  C)  B

5. Какое логическое выражение эквивалентно выражению
¬(¬A  B)  ¬C?
1)(A  B)  ¬C 2)(A  B)  C 3)(A  ¬B)  ¬C 4)(A  ¬B)  ¬C

гласная → Четвертая буква имени согласная)?
ЕЛЕНА 2) ВАДИМ 3) АНТОН 4) ФЕДОР

Для

какого символьного выражения неверно высказывание:
Первая буква гласная → ¬ (Третья буква согласная)?
1)abedc 2)becde 3) babas 4) abcab

3. Для какого имени истинно высказывание:
¬ (Первая буква имени согласная → Третья буква имени гласная)?
ЮЛИЯ 2) ПЕТР 3) АЛЕКСЕЙ 4) КСЕНИЯ

4. Для какого символьного выражения верно высказывание:
¬ (Первая буква согласная)  ¬ (Вторая буква гласная)?
abcde 2) bcade 3) babas 4) cabab

5. Для какого имени истинно высказывание:
(Вторая буква гласная → Первая буква гласная)  Последняя буква согласная?
1) ИРИНА 2) МАКСИМ 3) МАРИЯ 4) СТЕПАН

задания:

высказывание
¬((X > 2)→(X > 3))?
1)

1 2) 2 3) 3 4) 4
Решение:
определим порядок действий: сначала вычисляются результаты отношений в скобках, затем выполняется импликация (поскольку есть «большие» скобки), затем – отрицание (операция «НЕ») для выражения в больших скобках
выполняем операции для всех приведенных возможных ответов (1 обозначает истинное условие, 0 – ложное); сначала определяем результаты сравнения в двух внутренних скобках:
по таблице истинности операции «импликация» находим третий столбец (значение выражения в больших скобках), применив операцию «импликация» к значениям второго и третьего столбцов (в каждой строке):
значение выражения равно инверсии третьего столбца (меняем 1 на 0 и наоборот):
таким образом, ответ – 3.

истинно высказывание
((X < 5)→(X < 3))  ((X

< 2)→(X < 1))
1) 1 2) 2 3) 3 4) 4

2. Для какого числа X истинно высказывание ((X > 3)(X < 3)) →(X < 1)
1) 1 2) 2 3) 3 4) 4

3. Для какого числа X истинно высказывание X > 1  ((X < 5)→(X < 3))
1) 1 2) 2 3) 3 4) 4

4. Для какого из значений числа Z высказывание ((Z > 2)(Z > 4)) →(Z > 3) будет ложным?
1)1 2) 2 3) 3 4) 4

5. Для какого из значений числа Y высказывание (Y < 5)  ((Y > 1) → (Y > 5)) будет истинным?
1) 1 2) 2 3) 3 4) 4

= (А ↔ B)  ¬(A → (B 

C))
в которой столбец значений аргумента А представляет собой двоичную запись числа 27, столбец значений аргумента В – числа 77, столбец значений аргумента С – числа 120. Число в столбце записывается сверху вниз от старшего разряда к младшему. Переведите полученную двоичную запись значений функции X в десятичную систему счисления.

Решение
запишем уравнение, используя более простые обозначения операций:

это выражение с тремя переменными, поэтому в таблице истинности будет 23=8 строчек; следовательно, двоичная запись чисел, по которым строятся столбцы таблицы А, В и С, должна состоять из 8 цифр
переведем числа 27, 77 и 120 в двоичную систему, сразу дополняя запись до 8 знаков нулями в начале чисел
27 = 000110112 77 = 010011012 120 = 011110002
теперь можно составить таблицу истинности (см. рисунок справа), в которой строки переставлены в сравнении с традиционным порядком: зеленым фоном выделена двоичная записи числа 27 (биты записываются сверху вниз), синим – запись числа 77 и розовым – запись числа 120:
вряд ли вы сможете сразу написать значения функции Х для
каждой комбинации, поэтому удобно добавить в таблицу
Дополнительные столбцы для расчета промежуточных
результатов (см. таблицу ниже)

тех строчках, где А = В

значение

равно 1 только в тех строчках, где В = 1 или С = 1

значение равно 0 только в тех строчках, где А = 1 и В + С = 0

значение это инверсия предыдущего столбца (0 заменяется на 1, а 1–на 0)

результат Х (последний столбец) – это логическая сумма двух столбцов, выделенных фиолетовым фоном
чтобы получить ответ, выписываем биты из столбца Х сверху вниз: Х = 101010112
переводим это число в десятичную систему: 101010112 = 27 + 25 + 23 + 21 + 20 = 171
таким образом, правильный ответ – 171.

= (А → B)  (C ↔ ¬(B 

A))
в которой столбец значений аргумента А представляет собой двоичную запись числа 226, столбец значений аргумента В – числа 154, столбец значений аргумента С – числа 75. Число в столбце записывается сверху вниз от старшего разряда к младшему. Переведите полученную двоичную запись значений функции X в десятичную систему счисления.


2. Составьте таблицу истинности для логической функции
X = ¬(А → B)  (B ↔ ¬(C → A))
в которой столбец значений аргумента А представляет собой двоичную запись числа 216, столбец значений аргумента В – числа 30, столбец значений аргумента С – числа 170. Число в столбце записывается сверху вниз от старшего разряда к младшему. Переведите полученную двоичную запись значений функции X в десятичную систему счисления.

элементах И-НЕ или ИЛИ-НЕ.
И:
НЕ:
ИЛИ: