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

• 1. Понятие об алгебре высказываний
• 2. Составление логических формул
• 3. Основные законы алгебры логики
• 4. Составление таблиц истинности для логической формулы

Понятие об алгебре высказываний�

Алгеброй называется множество с определённым набором операций над его элементами, причём результат любой операции должен принадлежать этому же множеству.

Понятие алгебра - обобщённое, абстрактное. В школе, чтобы не мучить детишек, его не дают, но незаметно используют. В младших классах начинают изучать множество натуральных чисел и операции сложения и умножения, не выводящие за пределы этого множества. Дополнение набора операций вычитанием требует введения отрицательных чисел, а деления - действительных. Наконец, в старших классах рассматриваются комплексные числа и операции над ними.

аргументов, а в правой - соответствующие им значения функции.�

​

Алгебра логики возникла в середине ХIХ века в трудах английского математика Джорджа Буля. Ее создание представляло собой попытку решать традиционные логические задачи алгебраическими методами.

Логической функцией (функцией алгебры логики) от набора логических переменных F(х₁, ..., х_n) называется функция, которая может принимать только два значения: истина или ложь (1 или 0). Любая логическая функция может быть задана с помощью таблицы истинности, в левой части которой записываются возможные наборы значений.�

​

• Логическая переменная – это простое высказывание, содержащее только одну мысль. Ее символическое обозначение – латинская буква (например, A, B, X, Y и т.Д.). Значением логической переменной могут быть только константы истина (1) и ложь (0). На основании простых высказываний могут быть построены составные высказывания.
•    Логическая функция - составное высказывание, которое содержит несколько простых мыслей, соединенных между собой с помощью логических операций.
• Ее символическое обозначение – f (a, b, …).
• Логические операции – логическое действие. 

​

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

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

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

Свойства логических операций.

1

2

Алгебра логики

Логические операции

Дизъюнкция

Инверсия

Конъюнкция

Основные логические операции

Логические операции

A

B

A & B

0

0

0

0

0

0

0

1

1

1

1

1

Логические операции

A

B

A V B

0

0

0

0

0

1

1

1

1

1

1

1

Логические операции

А = 0

инверсия

А = 1

инверсия

Логические операции

Эквивалентность - логическое равенство.

Обозначение в алгебре высказываний: А<=>B.

​

 результат будет истинным тогда и только тогда, когда оба высказывания одновременно либо ложны, либо истинны

​

A

B

A <=> B

0

0

0

0

1

0

0

1

1

1

1

1

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

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

А V B & C

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

Порядок действий в

логическом выражении:

1. Скобки.
2. Инверсия.
3. Конъюнкция.
4. Дизъюнкция.

Для составления таблиц истинности необходимо:�

Основные свойства логических операций

Законы алгебры логики

1. Переместительный (коммутативный) закон.

При перестановке местами переменных в конъюнкции и дизъюнкции

значение выражения не изменяется.

A & B = B & A

Конъюнкция – логическое умножение.

A V B = B V A

Дизъюнкция – логическое сложение.

A • B = B • A

A + B = B + A

Основные свойства логических операций

Законы алгебры логики

2. Сочетательный (ассоциативный) закон.

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

вообще опускать.

(A & B) & C = A & (B & C)

Конъюнкция – логическое умножение.

(A V B) V C = A V (B V C)

Дизъюнкция – логическое сложение.

(A • B) • C = A • (B • C)

(A + B) + C = A + (B + C)

(A • B) • C = A • B • C

(A + B) + C = A + B + C

Основные свойства логических операций

Законы алгебры логики

3. Распределительный (дистрибутивный) закон.

A & (B V C) = (A & B) V (A & C)

Конъюнкция – логическое умножение.

A V (B & C) = (A V B) & (A V C)

Дизъюнкция – логическое сложение.

A • (B + C) = (A • B) + (A • C)

A + (B • C) = (A + B) • (A + C)

Основные свойства логических операций

Законы алгебры логики

4. Закон двойного отрицания.

A = A

– (– A) = A

Двойное отрицание исключает отрицание.

Основные свойства логических операций

Законы алгебры логики

5. Закон исключённого третьего.

A & A = 0

Конъюнкция – логическое умножение.

A V A = 1

Дизъюнкция – логическое сложение.

A = 0; A = 1; 0 • 1 = 0.

​

A = 1; A = 0; 1 • 0 = 0.

Из двух противоречивых высказываний об одном и том же предмете одно

всегда истинно, а второе – ложно, третьего не дано.

A = 0; A = 1; 0 + 1 = 1.

​

A = 1; A = 0; 1 + 0 = 1.

Основные свойства логических операций

Законы алгебры логики

6. Закон повторения.

A & A = А

Конъюнкция – логическое умножение.

A V A = А

Дизъюнкция – логическое сложение.

A = 0; 0 • 0 = 0.

​

A = 1; 1 • 1 = 1.

При конъюнкции или дизъюнкции одного и того же высказывания получится

это же высказывание.

A = 0; 0 + 0 = 0.

​

A = 1; 1 + 1 = 1.

A • A = А

A + A = А

Основные свойства логических операций

Законы алгебры логики

6. Закон повторения.

A & A = А

Конъюнкция – логическое умножение.

A V A = А

Дизъюнкция – логическое сложение.

A = 0; 0 • 0 = 0.

​

A = 1; 1 • 1 = 1.

При конъюнкции или дизъюнкции одного и того же высказывания получится

это же высказывание.

A • A = А

²

A = 0; 0 + 0 = 0.

​

A = 1; 1 + 1 = 1.

A + A = А

Основные свойства логических операций

Законы алгебры логики

7. Законы операций с 0 и 1.

A & 0 = 0; A • 0 = 0.

Конъюнкция – логическое умножение.

A V 0 = А; A + 0 = A.

Дизъюнкция – логическое сложение.

A & 1 = A; A • 1 = А.

A V 1 = 1; A + 1 = 1.

Основные свойства логических операций

Законы алгебры логики

8. Законы общей инверсии.

A & B = А V B

Конъюнкция – логическое умножение.

A V B = А & B

Дизъюнкция – логическое сложение.

Для того, чтобы найти инверсию конъюнкции, нужно найти дизъюнкцию

инверсий каждого логического выражения.

Для того, чтобы найти инверсию дизъюнкции, нужно найти конъюнкцию

инверсий каждого логического выражения.