Операция выражаемая связкой или

Общие теоретические сведения

Основные понятия алгебры логики

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

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

Логическое высказывание – это любое повествовательное предложение, в отношении которого можно однозначно сказать, истинно оно или ложно.

Не всякое предложение является логическим высказыванием.

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

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

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

Чтобы обращаться к логическим высказываниям, им назначают имена.

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

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

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

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

Тогда и только тогда

Исключающее ИЛИ (сложение по модулю 2)

. Высказывание А↔В истинно тогда и только тогда, когда значения А и В совпадают.

Вывод. Операций отрицания, дизъюнкции и конъюнкции достаточно, чтобы описывать и обрабатывать логические высказывания.

С помощью логических переменных и символов логических операций любое высказывание можно формализовать, то есть заменить логической формулой (логическим выражением).

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

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

Значения логической функции для разных сочетаний значений входных переменных – или, как это иначе называют, наборов входных переменных – обычно задаются специальной таблицей. Такая таблица называется таблицей истинности.

Алгоритм построения таблиц истинности для сложных выражений:

1. Определить количество строк:

• количество строк = 2 n + строка для заголовка,
• n - количество простых высказываний.

1. Определить количество столбцов:

• количество столбцов = количество переменных + количество логических операций;
• определить количество переменных (простых выражений);
• определить количество логических операций и последовательность их выполнения.

Существует три базовых логических элемента, которые реализуют три основные логические операции:

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

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

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

Чтобы обращаться к логическим высказываниям, им назначают имена.

Пусть через А обозначено высказывание “Тимур поедет летом на море”, а через В – высказывание “Тимур летом отправиться в горы”. Тогда составное высказывание “Тимур летом побывает и на море, и в горах” можно кратко записать как А и В. Здесь “и” – логическая связка, А.В – логические переменные, которые могут принимать только два значения – “истина” или “ложь”.

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

1. Логическое отрицание (инверсия)

Операция, выражаемая символом “не” называется отрицанием и обозначается чертой над высказыванием.

Логическое отрицание (инверсия) образуется из высказывания с помощью добавления частицы “не” к сказуемому или использования оборота речи “неверно, что”.

Обозначение: не А. (Более подробно об обозначениях логических операций смотрите в хранилище файлов)

Нас интересует истинность высказывания, имеющего форму не А. Определяется она по специальной таблице истинности.

Из таблицы истинности следует, что инверсия высказывания истинна, когда высказывание ложно, и ложна, когда высказывание истинно.

2. Логическое умножение (конъюнкция)

Операция, выражаемая связкой “и” называется конъюнкцией или логическим умножением.

Логическое умножение (конъюнкция) образуется соединением двух высказываний в одно с помощью союза “и”.

А = Закончились уроки.

В = Дети идут домой.

А * В = “Закончились уроки и дети идут домой”.

Обозначение конъюнкции: A и B, А*В.

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

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

3. Логическое сложение (дизъюнкция)

Операция, выражаемая связкой “или” называется дизъюнкцией или логическим сложением.

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

Высказывание “10 не делится на 2 или 5 не больше 3” - ложно, а высказывания

“10 делится на 2 или 5 больше 3”,

“10 делится на 2 или 5 не больше 3”

“10 не делится на 2 или 5 больше 3” - истинны.

Обозначение операции: А или В, A+B.

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

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

4. Логическое следование (импликация)

Каким образом импликация связывает два элементарных высказывания?

Пусть даны два высказывания:

А = “данный четырехугольник квадрат”.

В = “около данного четырехугольника можно описать окружность”.

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

Есть три варианта, когда импликация истинна:

· А истинно и В истинно, то есть данный четырехугольник квадрат, и около него можно описать окружность;

· А ложно и В ложно, то есть данный четырехугольник не является квадратом, но около него можно описать окружность (разумеется, это справедливо не для всякого четырехугольника);

· А ложно и В ложно, то есть данный четырехугольник не является квадратом, и около него нельзя описать окружность.

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

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

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

5. Логическое равенство (эквивалентность)

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

“24 делится на 6 тогда и только тогда, когда 24 делится на 3”,

“23 делится на 6 тогда и только тогда, когда 23 делится на 3”

истинны, а высказывания

“24 делится на 6 тогда и только тогда, когда 24 делится на 5”,

“21 делится на 6 тогда и только тогда, когда 21 делится на 3”

Высказывания А и В, образующие составное высказывание эквивалентность могут быть совершенно не связаны по содержанию, например: “три больше двух” (А), “пингвины живут в Антарктиде” (В). Отрицаниями этих высказываний являются высказывания “три не больше двух” (не А), “пингвины не живут в Антарктиде” (не В). Образованные из высказываний А, В составные высказывания А º В и не А º не В истинны, а высказывания А º не В и не А º В - ложны.

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

Итак, нами рассмотрены пять логических операций:

Импликацию можно выразить через дизъюнкцию и отрицание:

если А то В = не А + В

Эквиваленцию можно выразить через отрицание, дизъюнкцию и конъюнкцию:

А равносильно В = (не А + В) * (не В + А)

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

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

· отрицание

· конъюнкция

· дизъюнкция

· импликация

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

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

Выполните задания:

1. Определите, какие из высказываний в следующих парах являются отрицаниями друг друга, а какие нет:

Лекция 4. Булевая алгебра. Алгебра логики

4.1. Понятие высказывания. Простое и составное высказывание

4.2. Логические выражения и логические операции над высказываниями

4.3. Равносильность логических операций.

4.4. Формулы алгебры логики. Функции алгебры логики

4.5. Формы представления высказываний

4.6. Полнота системы булевых функций

4.7. Минимизация высказываний методом Квайна

Понятие высказывания. Простое и составное высказывание

Рассмотрим логику высказываний. Логика высказываний строится также, как и другие математические теории. В качестве основных понятий берется некоторый класс объектов, а также некоторые свойства, отношения и операции над этими объектами.

Основным объектом логики высказываний служат простые высказывания.

Определение. Высказывание — это повествовательное предложение, выражающее суждение. Если суждение, составляющее содержание (смысл) некоторого высказывания, истинно, то и о данном высказывании говорят, что оно истинно. В противном случае, если суждение, составляющее содержание некоторого высказывания, ложно, то и о данном высказывании говорят, что оно ложно.

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

1. Число 100 делится на 5. (Истина)

2. Число 3 больше числа 5. (Ложь)

3. Сегодня светит солнце. (Не является высказыванием)

4. Вечером мы пойдем в кино. (Не является высказыванием)

5. Я лгу. (Не является высказыванием)

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

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

Логические выражения и логические операции над высказываниями

Определение. Логическое выражение – это символическая запись, состоящая из логических величин (констант или переменных), объединенных логическими операциями (связками).

В булевой алгебре простым высказываниям ставятся в соответствие логические переменные, значение которых равно 1, если высказывание истинно, и 0, если высказывание ложно. Обозначаются логические переменные буквами латинского алфавита A, B, C, …, X, Y ,Z. Каждая логическая связка рассматривается как операция над логическими высказываниями и имеет свое название и обозначение. Действия логических операций будем представлять в виде таблиц истинности.

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

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

Высказывание
истинно, когда A ложно, и ложно, когда A истинно.

А: 7 делится на 5 без остатка.

ØА: Неверно, что 7 делится на 5 без остатка.

А	ØА
0	1
1	0

Эта таблица и принимается в качестве определения операции отрицания.

Высказывание А × В истинно тогда и только тогда, когда оба высказывания А и В истинны.

A. 6 делится на 3 без остатка (1);

B. 10 больше 5 (1);

C. 7 делится на 3 без остатка (0);

D. 3 больше 7 (0);

А	В	А&В
0	0	0
0	1	0
1	0	0
1	1	1

Эта таблица и принимается в качестве определения операции конъюнкции

Высказывание А
В ложно тогда и только тогда, когда оба высказывания А и В ложны.

A. 6 делится на 3 без остатка (1);

B. 10 больше 5 (1);

C. 7 делится на 3 без остатка (0);

D. 3 больше 7 (0);

A
B=1

A
D=1

C
D=0

А	В	А В
0	0	0
0	1	1
1	0	1
1	1	1

Эта таблица и принимается в качестве определения операции дизъюнкции.

А	В	А В
0	0	0
0	1	1
1	0	1
1	1	0

А	В	А В
0	0	1
0	1	1
1	0	0
1	1	1

,или
.

Высказывание
истинно тогда и только тогда, когда значения А и В совпадают.

7. Обратная конъюнкция И – НЕ (Штрих Шеффера ê)

А	В	А êВ
0	0	1
0	1	1
1	0	1
1	1	0

8. Обратная дизъюнкция ИЛИ – НЕ (Стрелка Пирса
, функция Вебба)

А	В	А В
0	0	1
0	1	0
1	0	0
1	1	0

Используя эти логические операции можно строить сколь угодно сложные высказывания. Приоритет выполнения операций: ⌐ & Ú

ê

П – пропускаете занятия;

Y – успешно занимаетесь;

Х – сдадите экзамен хорошо,

тогда все высказывание запишется:

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

Пусть A=1, B=0, C=0, D=1. Подставим эти значения в высказывание и получим:

Символы ⌐ & Ú

ê
называются пропозициональными связками,

А, В, С, … и т.д. – пропозициональными переменными.

Определение. Выражение, построенное из пропозициональных переменных с помощью пропозициональных связок, называется пропозициональной формой или формулой.

Определить значение истинности составного высказывания

D=А&(А&В

)
&В

при А=0, В=1, С=1

А&В=0, А&В
С=1

А&(А&В
С)=0

&В=1, D=1.

МОУ «Средняя общеобразовательная школа № 6

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

Учебное пособие по информатике

для 10 класса

Содержание

§1. Основы логики…………………………………..…….………3

§ 2. Логические операции……………………………..…..….…..5

§ 3. Логические формулы. Таблица истинности логической формулы……………………………………………..…..…. ….….8

§ 4. Основные законы алгебры логики. Упрощение логических формул……………………. ……………. ………11

§ 5. Решение логических задач…………………………. …….13

§ 6. Логическая функция…………………………. ………..….18

§ 7. Логические основы ЭВМ. Базовые логические элементы………………………………..………………………….21

§ 8. Логические элементы компьютера. Триггер и сумматор. 25

Вопросы для самоконтроля…………..……. …………….29

§ 1. Основы логики.

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

Логика – наука о законах и формах мышления.

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

К основным понятиям логики относятся следующие.

Логическое высказывание — это любое повествовательное предложение, в отношении кoтopoгo можно однoзначнo сказать, истинно oнo или лoжнo.

Так, например, предложение "6 — четное число" следует считать высказыванием, так как оно истинное. Предложение "Рим — столица Франции" тоже высказывание, так как оно ложное.

Утверждение — это суждение, которое требуется доказать или опровергнуть.

Например, любая теорема – это утверждение, требующее доказательства.

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

Например, ход доказательства какой-либо теоремы можно назвать рассуждением.

Умозаключение — это форма мышления, посредством которой из одного или нескольких суждений выводится новое суждение. Умозаключения бывают дедуктивные, индуктивные и по аналогии.

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

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

Разумеется, не всякое предложение является логическим высказыванием. Высказываниями не являются, например, предложения "ученик десятого класса" и "информатика — интересный предмет". Первое предложение ничего не утверждает об ученике, а второе использует слишком неопределённое понятие "интересный предмет". Вопросительные и восклицательные предложения также не являются высказываниями, поскольку говорить об их истинности или ложности не имеет смысла.

Предложения типа "в городе A более миллиона жителей", "у него голубые глаза" не являются высказываниями, так как для выяснения их истинности или ложности нужны дополнительные сведения: о каком конкретно городе или человеке идет речь. Такие предложения называются логическими выражениями.

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

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

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

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

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

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

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

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

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

Так, например, из элементарных высказываний "Петров — врач", "Петров — шахматист" при помощи связки "и" можно получить составное высказывание "Петров — врач и шахматист", понимаемое как "Петров — врач, хорошо играющий в шахматы".

При помощи связки "или" из этих же высказываний можно получить составное высказывание "Петров — врач или шахматист", понимаемое в алгебре логики как "Петров или врач, или шахматист, или и врач и шахматист одновременно".

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

Чтобы обращаться к логическим высказываниям, им назначают имена. Пусть через А обозначено высказывание "Тимур поедет летом на море", а через В — высказывание "Тимур летом отправится в горы". Тогда составное высказывание "Тимур летом побывает и на море, и в горах" можно кратко записать как А и В. Здесь "и" — логическая связка, А, В — логические переменные, которые могут принимать только два значения — "истина" или "ложь", обозначаемые, соответственно, "1" и "0".

Операция, выражаемая связкой "и", называется конъюнкцией (лат. conjunctio — соединение) или логическим умножением и обозначается точкой " . " (может также обозначаться знаками  или &).

Высказывание А . В истинно тогда и только тогда, когда оба высказывания А и В истинны.

Например, высказывание "10 делится на 2 и 5 больше 3" истинно, а высказывания "10 делится на 2 и 5 не больше 3", "10 не делится на 2 и 5 больше 3", "10 не делится на 2 и 5 не больше 3" — ложны.

Операция, выражаемая связкой "или" (в неисключающем смысле этого слова), называется дизъюнкцией (лат. disjunctio — разделение) или логическим сложением и обозначается знаком v (или плюсом).

Высказывание А v В ложно тогда и только тогда, когда оба высказывания А и В ложны.

Например, высказывание "10 не делится на 2 или 5 не больше 3" ложно, а высказывания "10 делится на 2 или 5 больше 3", "10 делится на 2 или 5 не больше 3", "10 не делится на 2 или 5 больше 3" — истинны.

Операция, выражаемая словом "не", называется логическим отрицанием или инверсией и обозначается чертой над высказыванием (или знаком  ).

Высказывание  А истинно, когда A ложно, и ложно, когда A истинно.

Например, "Луна — спутник Земли" (А) - истинно; "Луна — не спутник Земли" (  А) - ложно.

Операция, выражаемая связками "если . то", "из . следует", ". влечет . ", называется импликацией (лат. implico — тесно связаны) и обозначается знаком  .

Высказывание А  В ложно тогда и только тогда, когда А истинно, а В ложно.

Каким же образом импликация связывает два элементарных высказывания?

Покажем это на примере высказываний: "данный четырёхугольник — квадрат" (А) и "около данного четырёхугольника можно описать окружность"(В). Рассмотрим составное высказывание А  В, понимаемое как "если данный четырёхугольник квадрат, то около него можно описать окружность".

Есть три варианта, когда высказывание А  В истинно:

А истинно и В истинно, то есть данный четырёхугольник квадрат, и около него можно описать окружность;

А ложно и В истинно, то есть данный четырёхугольник не является квадратом, но около него можно описать окружность (разумеется, это справедливо не для всякого четырёхугольника);

A ложно и B ложно, то есть данный четырёхугольник не является квадратом, и около него нельзя описать окружность.

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

В обычной речи связка "если . то" описывает причинно-следственную связь между высказываниями. Но в логических операциях смысл высказываний не учитывается. Рассматривается только их истинность или ложность. Поэтому не надо смущаться "бессмысленностью" импликаций, образованных высказываниями, совершенно не связанными по содержанию. Например, такими: "если президент США — демократ, то в Африке водятся жирафы", "если арбуз — ягода, то в бензоколонке есть бензин".

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

Высказывание А  В истинно тогда и только тогда, когда значения А и В совпадают.

Например, высказывания "24 делится на 6 тогда и только тогда, когда 24 делится на 3", "23 делится на 6 тогда и только тогда, когда 23 делится на 3" истинны, а высказывания "24 делится на 6 тогда и только тогда, когда 24 делится на 5", "21 делится на 6 тогда и только тогда, когда 21 делится на 3" ложны.

Высказывания А и В, образующие составное высказывание А  В, могут быть совершенно не связаны по содержанию, например: "три больше двух" (А), "пингвины живут в Антарктиде" (В). Отрицаниями этих высказываний являются высказывания "три не больше двух" (  А), "пингвины не живут в Антарктиде" (  В). Образованные из высказываний А и В составные высказывания A  B и  A   B истинны, а высказывания A   B и  A  B — ложны.

§ 3. Логические формулы. Таблица истинности логической

формулы.

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

Определение логической формулы:

Всякая логическая переменная и символы "истина" ("1") и "ложь" ("0") — формулы.

Если А и В — формулы, то  A, А . В , А v В , А  B , А  В — формулы.

3. Никаких других формул в алгебре логики нет.

В п. 1 определены элементарные формулы; в п. 2 даны правила образования из любых данных формул новых формул.

В качестве примера рассмотрим высказывание "если я куплю яблоки или абрикосы, то приготовлю фруктовый пирог". Это высказывание формализуется в виде (A v B)  C. Такая же формула соответствует высказыванию "если Игорь знает английский или японский язык, то он получит место переводчика".

Как показывает анализ формулы (A v B)  C, при определённых сочетаниях значений переменных A, B и C она принимает значение "истина", а при некоторых других сочетаниях — значение "ложь". Такие формулы называются выполнимыми.

Некоторые формулы принимают значение "истина" при любых значениях истинности входящих в них переменных. Например, формула А v  А, соответствующая высказыванию "Этот треугольник прямоугольный или непрямоугольный" истинна и тогда, когда треугольник прямоугольный, и тогда, когда треугольник не прямоугольный. Такие формулы называются тождественно истинными формулами или тавтологиями. Высказывания, которые формализуются тавтологиями, называются логически истинными высказываниями.

В качестве другого примера рассмотрим формулу А .  А, которой соответствует, например, высказывание "Катя самая высокая девочка в классе, и в классе есть девочки выше Кати". Очевидно, что эта формула ложна, так как либо А, либо  А обязательно ложно. Такие формулы называются тождественно ложными формулами или противоречиями. Высказывания, которые формализуются противоречиями, называются логически ложными высказываниями.

Если две формулы А и В одновременно, то есть при одинаковых наборах значений входящих в них переменных, принимают одинаковые значения, то они называются равносильными.

Равносильность двух формул алгебры логики обозначается символом "=" Замена формулы другой, ей равносильной, называется равносильным преобразованием данной формулы.

Нами рассмотрены пять логических операций: отрицание, конъюнкция, дизъюнкция, импликация и эквиваленция.

Импликацию можно выразить через дизъюнкцию и отрицание:

А  В =  Аv В.

Эквиваленцию можно выразить через отрицание, дизъюнкцию и конъюнкцию:

А  В = (  А v В) . (  Вv А).

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

Порядок выполнения логических операций задается круглыми скобками. Но для уменьшения числа скобок договорились считать, что сначала выполняется операция отрицания ("не"), затем конъюнкция ("и"), после конъюнкции — дизъюнкция ("или") и в последнюю очередь — импликация.

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

Для формулы, которая содержит две переменные, таких наборов значений переменных всего четыре: (0, 0), (0, 1), (1, 0), (1, 1).

Если формула содержит три переменные, то таких наборов восемь: (0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1).

Количество наборов для формулы с четырьмя переменными равно шестнадцати и т.д. Т.е., если N – количество переменных, то 2 N – количество наборов значений переменных.

Таблица истинности элементарных логических формул