Краткие теоретические сведения. Алгебра логики (алгебра высказываний) – раздел математической логики

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

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

Чтобы обращаться к логическим высказываниям, им назначают имена. Например: А, В – логические переменные. Логические переменные могут иметь значения – «истина» или «ложь», обозначаемые, соответственно, «1» и «0».

Каждая логическая связка рассматривается как операция над логическими высказываниями и имеет свое название и обозначение (табл. 7).

Порядок выполнения логических операций в сложном логическом выражении: 1) инверсия; 2) конъюнкция; 3) дизъюнкция.

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

Истинность или ложность составных высказываний зависит от истинности или ложности элементарных высказываний.

Таблица 7- Логические связки

 

 

Математический аппарат алгебры логики очень удобен для описания того, как функционируют аппаратные средства компьютера:

1) одни и те же устройства компьютера могут применяться для обработки и хранения как числовой информации, представленной в двоичной системе счисления, так и логических переменных;

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

Основные законы логики

Логические выражения могут быть равносильно преобразованы из одной формы в другую согласно законам логики. Если две формулы А и В одновременно, то есть при одинаковых наборах значений входящих в них переменных, принимают одинаковые значения, то они называются равносильными. Равносильность двух формул алгебры логики обозначается символом «=» Замена формулы другой, ей равносильной, называется равносильным преобразованием данной формулы.

Таблица 8- Основные законы логики

Исходные данные

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

Таблица 9- Варианты заданий

Номер варианта	Задание 1	Задание 2
1	а	л
2	б	и
3	в	з
4	г	ж
5	д	е
6	е	д
7	ж	г
8	з	в
9	и	б
10	к	а

Задание 1. Найдите значения логических выражений:

а) ((1 V 1) & (1 V 1)) & 1 V 0;

б) ((0 V 0) V 1) V 1 & (0 V 1) V 0;

в) (0 V 1) V (1 V 0);

г) (0 & 1) & 1 V 1;

д) 1 & (1 & 1) & 1 V 1;

е) ((1 V 0) & (1 & 1)) & (0 V 1);

ж) ((1 & 0) V (1 & 0) V 1;

з) ((1 & 1) V 0) & (0 V 1);

и) ((0 & 0) V 0) & (1  V 1);

к) 0 & (1 & 1) & 0 & 1;

Задание 2. Упростите логическое выражение:

а) (A & B) V (A & B);

б) (A V B) & (A V C) &(A V B);

в) (A V B V C) & (A V B V C);

г) A & C V C&(B V C) V (A V B) & C;

д) A & (B V C) V A & B;

е) (A V C) (& A & C) & (A & C);

ж) (A V B) & (A V C) & (B V C);

з) A & (B V C) V A & B V A & C;

и) (A & C) & (B V C) & (B & C);

к) A & (B V C) V A & B;

л) (A V B) & (A V C) & (B V C).

Порядок выполнения

Нахождение значения логического выражения

((1 V 1) V (1 & 0)) & (1 V 1).

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

(1V 0)&1; 1&1. Ответ: истина (=1).

Алгоритм преобразования логических выражений

А V (А & В) = (A V А) & (A V B) = 1 & (A V B) = (1 & A) V (1 & B) = A V B.

1. Выполняем дизъюнкцию с каждым из высказываний в скобках.

2. Дизъюнкция A с инверсией А дает истину (=1) (по закону исключения третьего).

3. Выполняем конъюнкцию с каждым из высказываний в скобках.

4. Результатом конъюнкции высказывания с истиной является само высказывание.

Содержание отчета

1. Номер, название темы практического занятия.

2. Цель практического занятия.

3. Результаты выполнения работы: расчеты.

4. Выводы по работе.

Контрольные вопросы

1. Скажите, что изучает алгебра логики.

2. Поясните, что такое логическое высказывание.

3. Приведите примеры истинных и ложных, простых и сложных высказываний.

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

5. Укажите, в каком типе высказываний используются логические связки.

6. Скажите, что такое равносильные высказывания.

7. Вставьте недостающие слова в предложение: «Равносильное преобразование одного логического выражения в другое возможно согласно...».

8. Назовите основные законы алгебры логики.

 

 

Практическая работа 3

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

Цель: получить практические навыки и умения построения таблиц истинности.

Теоретические сведения

Для каждого логического выражения можно построить таблицу истинности, которая определяет его истинность или ложность при всех возможных комбинациях логических переменных. Три основных логических выражения представлены ниже (таблицы 10, 11, 12).

Логическое умножение – КОНЪЮНКЦИЯ – это новое сложное выражение, которое будет истинным только тогда, когда истинны оба исходных простых выражения. Конъюнкция определяет соединение двух логических выражений с помощью союза И.

 

Таблица 10- Таблица истинности для F = A & B

 

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

Логическое сложение – ДИЗЪЮНКЦИЯ – это новое сложное выражение, которое будет истинным тогда и только тогда, когда истинно хотя бы одно из исходных (простых) выражений. Дизъюнкция определяет соединение двух логических выражений с помощью союза ИЛИ.

Таблица 11 -Таблица истинности для F = A + B

 

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

Логическое отрицание – ИНВЕРСИЯ. Если исходное выражение истинно, то результат отрицания будет ложным, и наоборот, если исходное выражение ложно, то результат отрицания будет истинным. Данная операция означает, что к исходному логическому выражению добавляется частица НЕ или слова НЕВЕРНО, ЧТО.

 

Таблица 12 -Таблица истинности для F = А

 

A	F = А
0	1
1	0

Порядок выполнения