18.04.2024 / Логические основы компьютеров

• Логическое высказывание – это повествовательное предложение, относительно которого можно однозначно сказать, истинно оно (0) или ложно (1).

• Алгебра логики (булева алгебра) — это математический аппарат, с помощью которого записывают, вычисляют, упрощают и преобразуют логические высказывания.

• Логическое выражение — это символическая запись высказывания, которая может содержать логические переменные и знаки логических операций.

• Логическая функция — это правило преобразования входных логических значений в выходные. Логическая функция задаётся таблицей истинности.

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

• Операция НЕ (инверсия) Если высказывание A истинно, то «не А» ложно, и наоборот.

  A	not A
  0	1
  1	0

• Таблица истинности логического выражения Х — это таблица, где в левой части записываются все возможные комбинации значений исходных данных, а в правой – значение выражения Х для каждой комбинации.

• Операция И Высказывание «A и B» истинно тогда и только тогда, когда А и B истинны одновременно.

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

• Операция И (логическое умножение, конъюнкция)

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

• Операция ИЛИ (логическое сложение, дизъюнкция) Высказывание «A или B» истинно тогда, когда истинно А или B, или оба вместе.

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

• Операция ИЛИ (логическое сложение, дизъюнкция)

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

• Операция «исключающее ИЛИ» Высказывание «A  B» истинно тогда, когда истинно А или B, но не оба одновременно (то есть A ≠ B).

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

• Свойства операции «исключающее ИЛИ»

  A	B	A xor B	not(A xor B)
  0	0	0	1
  0	1	1	0
  1	0	1	0
  1	1	0	1

• Импликация («если …, то …») Высказывание «A → B» истинно, если не исключено, что из А следует B.

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

• Импликация («если …, то …)» «Если Вася идет гулять, то Маша сидит дома». A – «Вася идет гулять». B – «Маша сидит дома».

  Вася идет гулять	Маша сидит дома	Вася идет гулять → Маша сидит дома
  0	0	1
  0	1	1
  1	0	0
  1	1	1

• Эквиваленция («тогда и только тогда, …») Высказывание «A ⇔ B» истинно тогда и только тогда, когда А и B равны.

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

• Базовый набор операций С помощью операций И, ИЛИ и НЕ можно реализовать любую логическую операцию.

  A	B	NOT A	A AND B	A OR B
  0	0	1	0	0
  0	1	1	0	1
  1	0	0	0	1
  1	1	0	1	1

• Штрих Шеффера, «И-НЕ»

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

• Базовые операции через «И-НЕ»:

  • И: Выражение A AND B эквивалентно A | B

  • ИЛИ: Выражение A OR B эквивалентно (NOT A) | (NOT B)

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

Формализация

Прибор имеет три датчика и может работать, если два из них исправны. Записать в виде формулы ситуацию «авария».

• A – «Датчик № 1 неисправен».

• B – «Датчик № 2 неисправен».

• C – «Датчик № 3 неисправен».

Формализация – это переход к записи на формальном языке!

Аварийный сигнал:

• X – «Неисправны два датчика».

  • X – «Неисправны датчики № 1 и № 2» или

  • «Неисправны датчики № 1 и № 3» или

  • «Неисправны датчики № 2 и № 3».

Вычисление логических выражений

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

1. скобки

2. НЕ

3. И

4. ИЛИ, исключающее ИЛИ

5. импликация

6. эквиваленция

Таблица функции X = AB + A' B + B'

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

Ещё таблица X = A·B+A·C+B·C

A	B	C	X
1	0	0	1
0	0	0	0
1	1	1	1

Задачи

Задача 2

При каких значениях логических переменных ложно выражение: X₁ + X₂ + X₃ + X₄ + X₅.

Решение: Все слагаемые равны 0.

Задача 3

Запишите любое логическое выражение, соответствующее таблице истинности:

x	y	z	f
1	0	0	1
0	0	0	0
1	1	1	0

Ответ: Истинно при X = 1, Y = Z = 0. Таким образом, можно записать F = XYZ.

Задача 4

Запишите любое логическое выражение, соответствующее таблице истинности:

x	y	z	f
1	0	0	0
0	0	0	1
1	1	1	1

Ответ: Ложно при X = 1, Y = Z = 0. Таким образом, можно записать F = X + Y + Z.

Задача 5

Символом F обозначено одно из указанных ниже логических выражений от трёх аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F. Какое выражение соответствует F?

¬X ∧ ¬Y ∧ ¬Z X ∧ Y ∧ Z X ∨ Y ∨ Z ¬X ∨ ¬Y ∨ ¬Z

x	y	z	f
1	0	0	1
0	0	0	1
1	1	1	0

Быстрый способ: F = X + Y + Z