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

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

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

Построение таблицы истинности:

1. Количество строк N в таблице истинности равно количеству возможных комбинаций значений логических переменных n и определяется по формуле:

N = 2ⁿ.

2. Количество столбцов в таблице истинности равно количеству логических переменных плюс количество логических операций.

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

4. Заполнить таблицу истинности по столбцам, в соответствии с таблицами истинности.

Например, составим таблицу истинности для логического выражения

F = (AvB)&(AvB).

1) Количество переменных n=2, следовательно, количество строк N = 4.

2) Определим количество операций:

1 - (AvB).

2 - .

3 - .

4 - .

5 - .

Значит, таблица истинности будет иметь семь столбцов.

3) Построим исходную таблицу:

A	B

4. Воспользовавшись таблицами истинности логических элементов, заполним полученную таблицу по столбцам:

A	B

Таким образом можно определить значение любой логической функции.

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

Составное высказывание можно рассматривать как некую логическую функцию. Логическая функция двух аргументов имеет четыре возможных набора исходных значе­ний этих аргументов, то есть существует 16 различных логических функций двух аргументов:

Аргументы

Логические функции

A

B

F1

F2

F3

F4

F5

F6

F7

F8

F9

F10

F11

F12

F13

F14

F15

F16

Логическое следование (импликация) — это логическая функция, которую можно описать помощью оборота «если..., то...», и обозначается А -> В. Импликация связывает два простых логических выражения, из которых первое является условием (А), а второе (В)– следствием из этого условия. Результатом импликации является ЛОЖЬ только тогда, когда условие А истинно, а следствие В ложно.

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

A	B	А -> В

Логическое равенство (эквивалентность) — это логическая функция, которую можно описать c помощью оборота «тогда и только тогда, когда ...». Эквивалентность определяет результат сравнения двух простых логических выражений А и В. Результатом является новое логическое выражение, которое будет истинным тогда и только тогда, когда оба исходных выражения одновременно истинны или ложны. Обозначается символом "эквивалентности" – A ↔ B

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

A	B	А ↔ В

Логические законы

Закон тождества. Всякое высказывание тождественно самому себе:

А = А.

Закон непротиворечия. Высказывание не может быть одновременно истинным и ложным:

А & А = 0.

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

A v A = 1.

Закон двойного отрицания. Двойное отрицание дает в итоге исходное высказывание:

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

Закон коммутативности:

А & В = В & А

A v B = B v A

Закон ассоциативности:

(А & В) & С = А & (В & С)

(A v B) v C = A v (B v C)

Закон дистрибутивности. Отличается от подобного закона в алгебре — за скобки можно выносить не только об­щие «множители», но и общие «слагаемые»:

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

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

Базовые логические элементы

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

Логический элемент НЕ преобразует сигнал в противоположный, например, если на вход элемента подана логическая единица, то на выходе этого элемента будет логический ноль и наоборот. Графически выглядит следующим образом:

A	F

Логический элемент ИЛИ преобразует два сигнала, поданных на вход, в один сигнал на выходе по следующему принципу. Если на любой вход логического элемента ИЛИ будет подана логическая единица, то на выходе элемента будет логическая единица. Если на оба входа подан логический ноль, то на выходе элемента ИЛИ также будет ноль. Схематически логический элемент ИЛИ выглядит следующим образом:

A	B	F

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

A	B	F

На базе этих элементов строится логика ЭВМ.

Рассмотрим для примера, как можно построить устройство для сложения двух двоичных чисел — одноразрядный сумматор. Это устройство должно давать на выходе следующие сигналы:

0 + 0 = 00

0 + 1 = 01

1 + 0 = 01

1 + 1 = 10

Составим таблицу истинности для этого сумматора, обозначив входные сигналы (слагаемые) X и Y, а выходные – Р (сигнал переноса разряда) и Z:

X	Y	P	Z

Выходные сигналы описываются следующими логическими функциями:

Р = Х и Y

Z = (X или Y) и не (X и Y)

Логическая схема одноразрядного сумматора будет иметь вид:

Очевидно, что в компьютере используются многоразрядные сумматоры, которые состоят из одноразрядных сумматоров, соединенных следующим образом: на каждый разряд ставится одноразрядный сумматор, причем выход (перенос) сумматора младшего разряда подключается ко входу сумматора старшего разряда,

и т.д.

Глава 3