С. М. Горбенко (раздел 11), С. Ю. Кацко (раздел 4, 9, 10)

Алгебра логики – это раздел математики, изучающий высказывания, рассматриваемые со стороны их логических значений (истинности или ложности) и логических операций над ними. Логическое высказывание – это любое повествовательное предложение, в отношении которого можно однозначно сказать, истинно оно или ложно. Пример: «3 – простое число» является высказыванием, поскольку оно истинно. Не всякое предложение является логическим высказыванием. Пример: предложение «Давайте пойдем в кино» не является высказыванием. Вопросительные и побудительные предложения высказываниями не являются. Высказывательная форма – это повествовательное предложение, которое прямо или косвенно содержит хотя бы одну переменную и становится высказыванием, когда все переменные замещаются своими значениями. Пример: «x+2>5» - высказывательная форма, которая при x>3 является истинной, иначе ложной. Алгебра логики рассматривает любое высказывание только с одной точки зрения – является ли оно истинным или ложным. Слова и словосочетания «не», «и», «или», «если..., то», «тогда и только тогда» и другие позволяют из уже заданных высказываний строить новые высказывания. Такие слова и словосочетания называются логическими связками. Высказывания, образованные из других высказываний с помощью логических связок, называются составными (сложными). Высказывания, которые не являются составными, называются элементарными (простыми). Пример: высказывание «Число 6 делится на 2» - простое высказывание. Высказывание «Число 6 делится на 2, и число 6 делится на 3» - составное высказывание, образованное из двух простых с помощью логической связки «и». Истинность или ложность составных высказываний зависит от истинности или ложности элементарных высказываний, из которых они состоят. Чтобы обращаться к логическим высказываниям, им назначают имена. Пример: Обозначим через А простое высказывание «число 6 делится на 2», а через В простое высказывание «число 6 делится на 3». Тогда составное высказывание «Число 6 делится на 2, и число 6 делится на 3» можно записать как «А и В». Здесь «и» – логическая связка, А, В – логические переменные, которые могут принимать только два значения – «истина» или «ложь», обозначаемые, соответственно, «1» и «0». Каждая логическая связка рассматривается как операция над логическими высказываниями и имеет свое название и обозначение (табл. 1). Таблица 1. Основные логические операции Обозначение операции Читается Название операции Альтернативные обозначения ¬ НЕ Отрицание (инверсия) Черта сверху  И Конъюнкция (логическое умножение) ∙ &  ИЛИ Дизъюнкция (логическое сложение) + → Если … то Импликация  ↔ Тогда и только тогда Эквиваленция ~ XOR Либо …либо Исключающее ИЛИ (сложение по модулю 2)  НЕ Операция, выражаемая словом «не», называется отрицанием и обозначается чертой над высказыванием (или знаком ¬). Высказывание ¬А истинно, когда A ложно, и ложно, когда A истинно. Пример. Пусть А=«Сегодня пасмурно», тогда ¬А=«Сегодня не пасмурно». И Операция, выражаемая связкой «и», называется конъюнкцией (лат. conjunctio – соединение) или логическим умножением и обозначается точкой « · » (может также обозначаться знаками  или &). Высказывание А · В истинно тогда и только тогда, когда оба высказывания А и В истинны. Пример. Высказывание «Число 6 делится на 2, и число 6 делится на 3» - истинно, а высказывание «Число 6 делится на 2, и число 6 больше 10» - ложно. ИЛИ Операция, выражаемая связкой «или» (в неисключающем смысле этого слова), называется дизъюнкцией (лат. disjunctio – разделение) или логическим сложением и обозначается знаком  (или плюсом). Высказывание АВ ложно тогда и только тогда, когда оба высказывания А и В ложны. Пример. Высказывание «Число 6 делится на 2 или число 6 больше 10» - истинно, а высказывание «Число 6 делится на 5 или число 6 больше 10» - ложно. ЕСЛИ … ТО Операция, выражаемая связками «если …, то», «из … следует», «... влечет …», называется импликацией (лат. implico – тесно связаны) и обозначается знаком → . Высказывание А→В ложно тогда и только тогда, когда А истинно, а В ложно. Пример. Высказывание «если студент сдал все экзамены на «отлично», то он получит стипендию». Очевидно, эту импликацию следует признать ложной лишь в том случае, когда студент сдал на «отлично» все экзамены, но стипендии не получил. В остальных случаях, когда не все экзамены сданы на «отлично» и стипендия получена (например, в силу того, что студент проживает в малообеспеченной семье) либо когда экзамены вообще не сданы и о стипендии не может быть и речи, импликацию можно признать истинной. РАВНОСИЛЬНО Операция, выражаемая связками «тогда и только тогда», «необходимо и достаточно», «... равносильно …», называется эквиваленцией или двойной импликацией и обозначается знаком ↔ или ~ . Высказывание А↔В истинно тогда и только тогда, когда значения А и В совпадают. Пример. Высказывание «Число является четным тогда и только тогда, когда оно делится без остатка на 2» является истинным, а высказывание «Число является нечетным тогда и только тогда, когда оно делится без остатка на 2» - ложно. ЛИБО … ЛИБО Операция, выражаемая связками «Либо … либо», называется исключающее ИЛИ или сложением по модулю 2 и обозначается XOR или . Высказывание АВ истинно тогда и только тогда, когда значения А и В не совпадают. Пример. Высказывание «Число 6 либо нечетно либо делится без остатка на 2» является истинным, а высказывание «Либо число 6 четно либо число 6 делится на3» – ложно, так как истинны оба высказывания входящие в него. Замечание. Импликацию можно выразить через дизъюнкцию и отрицание: . Эквиваленцию можно выразить через отрицание, дизъюнкцию и конъюнкцию: . Исключающее ИЛИ можно выразить через отрицание, дизъюнкцию и конъюнкцию: Вывод. Операций отрицания, дизъюнкции и конъюнкции достаточно, чтобы описывать и обрабатывать логические высказывания. Порядок выполнения логических операций задается круглыми скобками. Но для уменьшения числа скобок договорились считать, что сначала выполняется операция отрицания («не»), затем конъюнкция («и»), после конъюнкции – дизъюнкция («или») и исключающего или и в последнюю очередь – импликация и эквиваленция. С помощью логических переменных и символов логических операций любое высказывание можно формализовать, то есть заменить логической формулой (логическим выражением). Логическая формула - это символическая запись высказывания, состоящая из логических величин (констант или переменных), объединенных логическими операциями (связками). Логическая функция - это функция логических переменных, которая может принимать только два значения: 0 или 1. В свою очередь, сама логическая переменная (аргумент логической функции) тоже может принимать только два значения: 0 или 1. Пример. – логическая функция двух переменных A и B. Значения логической функции для разных сочетаний значений входных переменных – или, как это иначе называют, наборов входных переменных – обычно задаются специальной таблицей. Такая таблица называется таблицей истинности. Приведем таблицу истинности основных логических операций (табл. 2) Таблица 2. A B 1 1 0 1 1 1 1 0 1 0 0 0 1 0 0 1 0 1 1 0 1 1 0 1 0 0 1 0 0 1 1 0 Опираясь на данные таблицы истинности основных логических операций можно составлять таблицы истинности для более сложных формул. Алгоритм построения таблиц истинности для сложных выражений: Определить количество строк: количество строк = 2n + строка для заголовка, n - количество простых высказываний. Определить количество столбцов: количество столбцов = количество переменных + количество логических операций; определить количество переменных (простых выражений); определить количество логических операций и последовательность их выполнения. Заполнить столбцы результатами выполнения логических операций в обозначенной последовательности с учетом таблиц истинности основных логических операций. Пример 1. Составить таблицу истинности для формулы И–НЕ, которую можно записать так: . Определить количество строк: На входе два простых высказывания: А и В, поэтому n=2 и количество строк =22+1=5. Определить количество столбцов: Выражение состоит из двух простых выражений (A и B) и двух логических операций (1 инверсия, 1 конъюнкция), т.е. количество столбцов таблицы истинности = 4. Заполнить столбцы с учетом таблиц истинности логических операций (табл. 3). Таблица 3. Таблица истинности для логической операции A B 1 1 1 0 1 0 0 1 0 1 0 1 0 0 0 1 Подобным образом можно составить таблицу истинности для формулы ИЛИ–НЕ, которую можно записать так: . Таблица 4. Таблица истинности для логической операции A B 1 1 1 0 1 0 1 0 0 1 1 0 0 0 0 1 Примечание: И–НЕ называют также «штрих Шеффера» (обозначают | ) или «антиконъюнкция»; ИЛИ–НЕ называют также «стрелка Пирса» (обозначают ↓) или «антидизъюнкция». Пример 2. Составить таблицу истинности логического выражения . Решение: Определить количество строк: На входе два простых высказывания: А и В, поэтому n=2 и количество строк=22+1= 5. Определить количество столбцов: Выражение состоит из двух простых выражений (A и B) и пяти логических операций (2 инверсии, 2 конъюнкции, 1 дизъюнкция), т.е. количество столбцов таблицы истинности = 7. Сначала выполняются операции инверсии, затем конъюнкции, в последнюю очередь операция дизъюнкции. Заполнить столбцы с учетом таблиц истинности логических операций (табл. 5). Таблица 5. Таблица истинности для логической операции A B C 1 1 0 0 0 0 0 1 0 0 1 0 1 1 0 1 1 0 1 0 1 0 0 1 1 0 0 0 Логические формулы можно также представлять с помощью языка логических схем. Существует три базовых логических элемента, которые реализуют три основные логические операции: логический элемент «И» – логическое умножение – конъюнктор; логический элемент «ИЛИ» – логическое сложение – дизъюнктор; логический элемент «НЕ» – инверсию – инвертор. конъюнктор дизъюнктор инвертор Поскольку любая логическая операция может быть представлена в виде комбинации трех основных, любые устройства компьютера, производящие обработку или хранение информации, могут быть собраны из базовых логических элементов, как из “кирпичиков”. Логические элементы компьютера оперируют с сигналами, представляющими собой электрические импульсы. Есть импульс – логический смысл сигнала – 1, нет импульса – 0. На входы логического элемента поступают сигналы-значения аргументов, на выходе появляется сигнал-значение функции. Преобразование сигнала логическим элементом задается таблицей состояний, которая фактически является таблицей истинности, соответствующей логической функции, только представлена в форме логических схем. В такой форме удобно изображать цепочки логических операций и производить их вычисления.

Похожие:

	Генеральной прокуратуры российской федерации прокурорский надзор... Н. П. Дудин — раздел 1; О. Б. Качанова — разделы 2, 5, 8, 11; раздел 13 в соавторстве; Н. Я. Ларина — раздел 6; О. В. Пристанская,...		Программа по формированию навыков безопасного поведения на дорогах... Фгоу впо сибгути. Раздел 1 Основы теории множеств. Раздел 2 Формулы логики. Раздел 3 Булевы функции. Раздел 4 Предикаты и бинарные...
	Учебно-методический комплекс дисциплины «физическая культура» Т. В. Никольская, О. Ю. Масалова (раздел гимнастика); Т. Н. Хатанцева, Е. П. Панова, Ю. В. Булков (раздел легкая атлетика); А. Б....		Учебное пособие Для студентов вузов в 2-х частях С. К. Ашванян, д-р экон наук, проф. (раздел 4,7); Т. А. Сапожникова, канд экон наук, доц. (введение, раздел 5,9 ); Е. А. Плосконосова,...
	Несовершеннолетних Авторский коллектив: Арбузова В. Н. ), Завадская Н. М. ), Карабанцев И. А. ), Кряквин В. Я. ), Кудрявцева Г. А. (раздел I, тематика...		История россии М. М. Горинов (раздел II гл. 5 § 1 — 5), докт ист наук А. С. Сенявский (раздел II гл. 5 § 6), канд ист наук А. А. Печенкин (раздел...
	Программа «проведения аттестационных испытаний при поступлении на второй и последующие курсы» Ий при поступлении на второй и последующие курсы включает в себя 4 раздела: 1 раздел – гуманитарный, социальный и экономический цикл;...		Программа состоит из девяти разделов: Раздел Искусство в жизни современного... Данная рабочая программа разработана на основе авторской программы Г. П. Сергеевой, И. А. Кашековой, Е. Д. Критской «Искусство. 8...
	Учебно-методический комплекс по дисциплине «бизнес-планирование» Разработка основных разделов бизнес-плана: план маркетинга. Производственный план предприятия как раздел бизнес-плана. Организационный...		Тема: Насекомые. Изделие "Пчелы и соты" Межпредметные связи: Окружающий мир, раздел "Что и кто?", тема "Кто такие насекомые?"; раздел "Почему и зачем?", тема "Почему мы...
	Цели и задачи территориального планирования Раздел Мероприятия по... Схема современного использования территории мо «Мултановский сельсовет» (Опорный план)		Учебно-тематический план Раздел 3 содержание учебного предмета «Литература»... Примерная программа среднего (полного) общего образования по литературе (Москва, Дрофа, 2007г)
	Программа по формированию навыков безопасного поведения на дорогах... Рабочая программа по русскому языку (раздел «Письмо») и литературному чтению (раздел «Обучение грамоте») разработана на основе		Программа по формированию навыков безопасного поведения на дорогах... Межпредметные связи: Окружающий мир, раздел "Что и кто?", тема "Кто такие звери?"; раздел "Как, откуда и куда?", тема "Как живут...
	Рабочая программа дисциплины судебная психиатрия цикл «опд»; раздел «В. 31» «опд»; раздел «В. 31»; основная образовательная программа специальности 030501. 65 Юриспруденция		Содержание программы раздел I пояснительная записка (цели и задачи... Учебно-методическое и материально-техническое обеспечение образовательного процесса