Информатика: аппаратные средства персонального компьютера

истинным.

Математическая запись данной операции для логических переменных A, В, С, … будет иметь вид:

F = AvBvC…

4. Логическая операция ИМПЛИКАЦИЯ (логическое следование). В естественных языках соответствует обороту речи, если…, то …, в языках программирования обозначается If, в алгебре логики обозначается  ?.

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

Математическая запись данной операции для двух логических переменных А и В будет иметь вид:

F = A?B.

5. Логическая операция ЭКВИВАЛЕНЦИЯ (логическая равнозначность). В естественных языках соответствует обороту речи тогда и только тогда, в алгебре логики обозначается ?.

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

Математическая запись данной операции для логических переменных A, В, С… будет иметь вид:

F = A?B?C?…

4.2. Основные законы алгебры логики и правила преобразования логических выражений

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

Для простоты записи приведем основные законы алгебры логики для двух логических переменных А и В. Эти законы распространяются и на другие логические переменные.

1. Закон противоречия:

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

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

4. Законы де Моргана:

5. Законы повторения: A & A = A; A v A = A; В & В = В; В v В = В.

6. Законы поглощения: A ? (A & B) = A; A & (A ? B) = A.

7. Законы исключения констант: A ? 1 = 1; A ? 0 = A; A & 1 = A; A & 0 = 0; B ? 1 = 1; B ? 0 = B; B & 1 = B; B & 0 = 0.

8. Законы склеивания:

9. Закон контрапозиции: (A ? B) = (B ? A).

Для логических переменных справедливы и общематематические законы. Для простоты записи приведем общематематические законы для трех логических переменных A, В и С:

1. Коммутативный закон: A & B = B & A; A ? B = B ? A.

2. Ассоциативный закон: A & (B & C) = (A & B) & C; A ? (B ? C) = (A ? B) ? C.

3. Дистрибутивный закон: A & (B ? C) = (A & B) ? (A & C).

Как уже отмечалось, с помощью законов алгебры логики можно производить равносильные преобразования логических выражений с целью их упрощения. В алгебре логики на основе принятого соглашения установлены следующие правила (приоритеты) для выполнения логических операций: первыми выполняются операции в скобках, затем в следующем порядке: инверсия (отрицание), конъюнкция ( & ), дизъюнкция (v), импликация (?), эквиваленция (?)

Выполним преобразование, например, логической функции

применив соответствующие законы алгебры логики.

4.3. Логические функции и таблицы истинности

Соотношения между логическими переменными и логическими функциями в алгебре логики можно отобразить также с помощью соответствующих таблиц, которые носят название таблиц истинности. Таблицы истинности находят широкое применение, поскольку наглядно показывают, какие значения принимает логическая функция при всех сочетаниях значений ее логических переменных. Таблица истинности состоит из двух частей. Первая (левая) часть относится к логическим переменным и содержит полный перечень возможных комбинаций логических переменных А, В, С… и т. д. Вторая (правая) часть этой таблицы определяет выходные состояния как логическую функцию от комбинаций входных величин.

Например, для логической функции F = A v B v C (дизъюнкции) трех логических переменных А, В, и С таблица истинности будет иметь вид, показанный на рис. 4.1. Для записи значений логических переменных и логической функции данная таблица истинности содержит 8 строк и 4 столбца, т. е. число строк для записи значений аргументов и функции любой таблицы истинности будет равно 2ⁿ, где п – число аргументов логической функции, а число столбцов равно п + 1.

Рис. 4.1. Таблица истинности для логической функции F = A v В v С

Таблицу истинности можно составить для любой логической функции, например, на рис. 4.2 приведена таблица истинности логической функции F = A ? B ? C (эквиваленции).

Логические функции имеют соответствующие названия. Для двух двоичных переменных существует шестнадцать логических функций, названия которых приведены ниже. На рис. 4.3 представлена таблица, в которой приведены логические функции F₁, F₂, F₃, … , F₁₆ двух логических переменных A и В.

Функция F₁ = 0 и называется функцией константы нуля, или генератора нуля.

Рис. 4.2. Таблица истинности для логической функции F = A ? B ? C

Рис. 4.3. Логические функции F₁, F₂, F₃,… F₁₆ двух аргументов А и В

Функция F₂ = A & B называется функцией конъюнкции.

Функция

называется функцией запрета по логической переменной А.

Функция F₄ = А называется функцией повторения по логической переменной А.

Функция