Учебный курс «Информатика»

Алгебра логики

Логические элементы

Построение комбинационных схем

Арифметико-логическое устройство

Моделирование памяти. Триггер

Вопросы и упражнения

    Логика очень древняя наука. Ещё в античные времена была известна формальная логика, позволяющая делать заключения о правильности какого-либо суждения не по его фактическому содержанию, а только по форме его построения. Например, уже в древности был известен закон исключения третьего. Его содержательная трактовка была такова: «Во время своих странствований Платон был в Египте ИЛИ не был Платон в Египте». В такой форме это или любое другое выражение будут правильны (тогда говорили: истинно). Ничего другого быть не может: Платон либо был, либо не был в Египте — третьего не дано.

    Другой закон логики — закон непротиворечивости. Если сказать: «Во время своих странствий Платон был в Египте И не был Платон в Египте», то очевидно, любое высказывание, имеющее такую форму, всегда будет ложно. Если из теории следуют два противоречащих друг другу вывода, то такая теория безусловно неправильная (ложная) и должна быть отвергнута.
    Ещё один закон, известный в древности — закон отрицания: «Если НЕ верно, что Платон НЕ был в Египте, то значит, Платон был в Египте».
    Формальная логика основана на “высказываниях”. “Высказывание” — это основной элемент логики, определяемый как повествовательное предложение, относительно которого можно однозначно сказать, истинное или ложное утверждение оно содержит.

    Например: Листва на деревьях опадает осенью. Земля прямоугольная.
    Первое высказывание содержит истинную информацию, а второе — ложную. Вопросительное, побудительное и восклицательное предложения не являются высказываниями, так как в них ничего не утверждается и не отрицается.
    Пример предложений, не являющихся высказываниями: Не пейте сырую воду! Кто не хочет быть счастливым?
    Высказывания могут быть и такими: 2>1, Н2О+SO3=h3SO4. Здесь используются языки математических символов и химических формул.
    Приведённые выше примеры высказываний являются простыми. Но из простых высказываний можно получить сложные, объединив их с помощью логических связок. Логические связки — это слова, которые подразумевают определённые логические связи между высказываниями. Основные логические связки издавна употребляются не только в научном языке, но и в обыденном, — это “и”, “или”, “не”, “если … то”, “либо … либо” и другие известные нам из русского языка связки. В рассмотренных нами трёх законах формальной логики использовались связки “и”, “или”, “не”, “если … то” для связи простых высказываний в сложные.
    Высказывания бывают общими, частными и единичными. Общее высказывание начинается со слов: всё, все, всякий, каждый, ни один. Частное высказывание начинается со слов: некоторые, большинство и т.п. Во всех других случаях высказывание является единичным.
    Формальная логика была известна в средневековой Европе, она развивалась и обогащалась новыми законами и правилами, но при этом вплоть до 19 века она оставалась обобщением конкретных содержательных данных и её законы сохраняли форму высказываний на разговорном языке.

    В 1847 году английский математик Джордж Буль, преподаватель провинциального университета в маленьком городке Корке на юге Англии разработал

алгебру логики.
    Алгебра логики очень проста, так как каждая переменная может принимать только два значения: истинно или ложно. Трудность изучения алгебры логики возникает из-за того, что для обозначения переменных принимают символы 0 и 1, которые по написанию совпадают с обычными арифметическими единицей и нулём. Но совпадение это только внешнее, так как смысл они имеют совсем иной.
    Логическая 1 означает, что какое-то событие истинно, в противоположность этому логический 0 означает, что высказывание не соответствует истине, т.е. ложно. Высказывание заменилось на логическое выражение, которое строится из логических переменных (А, В, Х, …) и логических операций (связок).
    В алгебре логики знаки операций обозначают лишь три логические связки ИЛИ, И, НЕ.
    1.Логическая операция ИЛИ. Логическую функцию принято задавать в виде таблицы. В левой части этой таблицы перечисляются все возможные значения аргументов функции, т.е. входные величины, а в правой указывается соответствующее им значение логической функции. Для элементарных функций получается таблица истинности данной логической операции. Для операции ИЛИ таблица истинности имеет вид:

    Операцию ИЛИ называют также логическим сложением, и потому её можно обозначать знаком «+».
    Рассмотрим сложное единичное высказывание: «Летом я поеду в деревню или в туристическую поездку». Обозначим через

А простое высказывание «Летом я поеду в деревню», а через В — простое высказывание «Летом я поеду в туристическую поездку». Тогда логическое выражение сложного высказывания имеет вид А+В, и оно будет ложным только, если ни одно из простых высказываний не будет истинным.
    2. Логическая операция И. Таблица истинности для этой функции имеет вид:

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

И можно обозначить знаком по-разному:

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

    Читается в обоих случаях одинаково «Не А». Таблица истинности для этой функции имеет вид:

    В вычислительной технике операцию НЕ называют отрицанием или инверсией

, операцию ИЛИ — дизъюнкцией, операцию И — конъюнкцией. Набор логических функций “И”, “ИЛИ”, “НЕ” является функционально полным набором или базисом алгебры логики. С помощью него можно выразить любые другие логические функции, например операции “строгой дизъюнкции”, “импликации” и “эквивалентности” и др. Рассмотрим некоторые из них.
    Логическая операция “строгая дизъюнкция”. Этой логической операции соответствует логическая связка “либо … либо”. Таблица истинности для этой функции имеет вид:

    Операция “строгая дизъюнкция” выражается через логические функции “И”, “ИЛИ”, “НЕ” любой из двух логических формул:

и иначе называется операцией неравнозначности или “сложения по модулю 2”, так как при сложении чётного количества единиц, результатом будет “0”, а при сложении нечётного числа единиц, результат станет равен “1”.
    Логическая операция “импликация”. Выражение, начинающееся со слов если, когда, коль скоро и продолжающееся словами то, тогда, называется условным высказыванием или операцией «импликация». Таблица истинности для этой функции имеет вид:

    Операцию “импликация” можно обозначить по-разному:

    Эти выражения эквивалентны и читаются одинаково: «Игрек равен импликации от А и В». Операция “импликация” выражается через логические функции “ИЛИ”, “НЕ” в виде логической формулы

    Логическая операция “эквивалентность” (равнозначность). Этой логической операции соответствуют логические связки “если и только если”, «тогда и только тогда, когда». Таблица истинности для этой функции имеет вид:

    Операция “эквивалентность” обозначается по-разному. Выражения

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

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

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

    Примеры использования основных аксиом и законов:

Элементы алгебры логики

---

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

Разобраться в алгебре логике поможет программа «Осваиваем основы алгебры логики«

---

Компьютерная программа «Осваиваем основы алгебры логики»

Эта программа позволяет интерактивно закрепить материал по основам алгебры логики. Будет удобна для 7-11 классов.

• тренировка с кругами Эйлера
• задания на круги Эйлера
• задания на поисковые запросы (значения множеств)

---

Основоположником логики считается Аристотель, живший до нашей эры (384-322 до н. э.).

С наукой логикой также связаны имена Джордж Буль, который создал алгебру высказывания или Булеву алгебру. Так же Клод Шеннон, который применил алгебру логику в вычислительной технике.

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

Пример.

Земля вращается вокруг солнца — это высказывание истинно.

Ни одна птица не летает — это высказывание ложно.

Не всякое повествовательное предложение является высказыванием. Побудительные и вопросительные предложения определенно высказываниями не являются.

Без стука не входить!

Откройте учебники!

Ты выучил стихотворение?

Алгебра логики определяет правила записи, вычисления значений, упрощения и преобразования высказываний.

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

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

0 и 1 это логические значения.

Высказывания бывают простые и сложные.

Высказывание простое если никакая его часть сама не является высказыванием.

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

---

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

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

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

Обозначения: НЕ А, ¬ А, Ā, not

Вы вправе выбирать любое обозначение какое вас устраивает. В языке программирования инверсия обозначается not. На естественном языке логическое отрицание формулируется с помощью слов связок.

«НЕ»; «НЕВЕРНО, ЧТО»

Значение логических операций отражается в таблице истинности.

Если высказывание А следующее. Вы ученики 10 класса. Оно ложное А = 0, тогда его инверсия будет истина Ā = 1., •, &, И, and

На языке программирования and.

На естественном языке «И»; «А»; «НО»; «ХОТЯ».

Рассмотрим таблицу истинности.

Конъюнкция истинна тогда, когда оба простых высказывания будет истинно. Например, вы ученики восьмого класса А = 1 и живете в Самаре B = 1. В случае если одно из простых высказываний ложно тогда и конъюнкция будет ложной.

---

3. Логическая операция дизъюнкция — логическое сложение.

Обозначение: V, |, ИЛИ, +, or

На языке программирования or

На естественном языке «ИЛИ», «ЛИБО»

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

Вы ученики пятого класса А = 1 или живете в Самаре B = 1.

Дизъюнкция ложна в случае, когда все простые высказывания ложны.

Подведем итог.

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

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

Дизъюнкция истина, когда хотя бы одно простое высказывание истинно.

---

§18. Алгебра логики | Логические операции (курс фгос 34 ч.)

		18.2. Логические операции
	18.1. Логические высказывания и переменные		18.3. Логические выражения

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

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

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

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

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

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

При построении отрицания простого высказывания:

• используется оборот «неверно, что» или к сказуемому добавляется частица «не»;
• в высказывании, содержащем слово «все», это слово заменяется на «некоторые» и наоборот.

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

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

Операция импликации обозначается символом → и задаётся следующей таблицей истинности:

В разговорной речи импликации соответствуют предложения, содержащие связку «если …, то». Эту связку мы используем тогда, когда хотим показать наличие причинно-следственной связи, иначе говоря, зависимость одного события от другого. Например, пусть некоторый человек сказал: «Если завтра будет хорошая погода, то я пойду гулять». Ясно, что человек окажется лжецом лишь в том случае, если погода действительно будет хорошей, а гулять он не пойдёт. Если же погода будет плохой, то, независимо от того, пойдёт он гулять или нет, во лжи его нельзя обвинить: обещание пойти гулять он давал лишь при условии, что погода будет хорошей.

Результат операции импликации, как и других логических операций, определяется истинностью или ложностью логических переменных, а не наличием причинно-следственных связей между высказываниями. Например, абсурдное с житейской точки зрения высказывание «Если 2 > 3, то существуют ведьмы» является истинным с точки зрения алгебры логики.

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

Строгая дизъюнкция обозначается символом ⊕ и задаётся следующей таблицей истинности:

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

Например, высказывая утверждение «На сегодняшнем матче Петя сидит на трибуне А либо на трибуне Б», мы считаем, что Петя сидит либо только на трибуне А, либо только на трибуне Б, и что сидеть одновременно на двух трибунах Петя не может.

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

В логике эквиваленция обозначается символом и задаётся следующей таблицей истинности:

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

Рассмотрим высказывание «Денис пойдёт в бассейн тогда и только тогда, когда он выучит уроки».

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

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

Можно сделать выводы:

• операция эквиваленции есть отрицание операции строгой дизъюнкции ;
• операция строгой дизъюнкции есть отрицание операции эквиваленции .

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

Таблица 4.1

Логические операции и их обозначения

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

 

Дизъюнкция, нестрогая дизъюнкция, логическое сложение, операция ИЛИ, операция OR.

`|«, vv, +`

Строгая дизъюнкция, разделительная дизъюнкция, исключающее ИЛИ, сложение по модулю `2`.

`o+, Delta`

Эквивалентность, эквиваленция, равенство, равнозначность.

`iff, -=`

Импликация, следование, следствие

`=>, ->`

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

Для того, чтобы не путаться и гарантированно перебрать все возможные комбинации значений операндов, принято записывать их в лексикографическом порядке (условно считается, что «ложь» `<` «истина»).

Таблица истинности для конъюнкции

Первый операнд	Второй операнд	Значение операции
`0`	`0`	`bb0`
`0`	`1`	`bb0`
`1`	`0`	`bb0`
`1`	`1`	`bb1`

 

Таблица истинности для дизъюнкции

Первый операнд	Второй операнд	Значение операции
`0`	`0`	`bb0`
`0`	`1`	`bb1`
`1`	`0`	`bb1`
`1`	`1`	`bb1`

 

Таблица истинности для строгой дизъюнкции

Первый операнд	Второй операнд	Значение операции
`0`	`0`	`bb0`
`0`	`1`	`bb1`
`1`	`0`	`bb1`
`1`	`1`	`bb0`

Таблица истинности для эквивалентности

Первый операнд	Второй операнд	Значение операции
`0`	`0`	`bb1`
`0`	`1`	`bb0`
`1`	`0`	`bb0`
`1`	`1`	`bb1`

 

Таблица истинности для импликации

Первый операнд	Второй операнд	Значение операции
`0`	`0`	`bb1`
`0`	`1`	`bb1`
`1`	`0`	`bb0`
`1`	`1`	`bb1`

                 

Таблица истинности для отрицания

Значение операнда	Значение операции
`0`	`bb1`
`1`	`bb0`

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

Логическая операция	Логические связки в русском языке
Отрицание	Неверно что…
Конъюнкция	и, а, но,  а также, при этом, одновременно с этим, хотя
Дизъюнкция	Или
Строгая дизъюнкция	или, либо
Эквивалентность	Тогда и только тогда когда, необходимо и достаточно чтобы
Импликация	если то, необходимо чтобы, достаточно чтобы

Обратите внимание, что союз ИЛИ может означать, как строгую, так и нестрогую дизъюнкцию. Его интерпретация зависит от содержания (!!!) высказывания.

 Рассмотрим высказывание: «Мы идём в кино в субботу или в воскресение». Здесь два простых высказывания: «Мы идём в кино в субботу» и «Мы идём в кино в воскресение». Между ними стоит союз ИЛИ, который можно интерпретировать двояко. В данном случае очевидно, что мы можем пойти в кино и в субботу, и в воскресение, поэтому дизъюнкция будет нестрогая. Возьмём две логические переменные – `p` и `q` и присвоим им простые высказывания. Тогда исходное высказывание в формализованном виде будет выглядеть, как `bb(pvvq)`.

Рассмотрим высказывание: «Я сейчас на севере Москвы или на юго-западе Москвы». Здесь тоже два простых высказывания, которые связаны союзом ИЛИ. Но в этом случае союз ИЛИ интерпретируется, как строгая дизъюнкция, поскольку нельзя одновременно находиться в двух местах. Таким образом, если снова взять логические переменные `p` и `q`, то получится следующая логическая формула: `bb(p»o+q)`.

Рассмотрим высказывание: «Для того чтобы четырёхугольник был квадратом, необходимо, чтобы все его стороны были равны». Здесь два простых высказывания: «Четырёхугольник является квадратом» и «Все стороны четырёхугольника равны». Присвоим их соответственно логическим переменным `p` и `q`. Логическая связка «необходимо, чтобы» — это импликация. Весь вопрос в том, что из чего следует. (Какая запись правильная: `bbp -> bbq` или `bbq ->bbp`?)  Импликация ложна только в единственном случае: когда левый операнд имеет значение «истина», а правый – «ложь». Рассмотрим все возможные значения операндов и проанализируем, какая из ситуаций невозможна.

1) `p` и `q` ложны. Это значит, что четырёхугольник не является квадратом и его стороны не равны. Это возможная ситуация.

2) `p` – ложно, `q` – истинно. Это значит, что четырёхугольник не является квадратом, но стороны у него равны. Это возможно (ромб).

3) `p` – истинно, `q` – истинно. Это значит, что четырёхугольник является квадратом и стороны у него равны. Это возможная ситуация.

4) `p` – истинно, `q` – ложно. Это значит, что четырёхугольник является квадратом, но стороны у него не равны. Это невозможная ситуация.

Анализ ситуаций показывает, что левым операндом импликации должна быть переменная `p`. Таким образом, в формализованном виде исходное высказывание выглядит как `bb(p -> q)`.

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

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

Чаще всего используются следующие логические операции:

• инверсия (отрицание, логическое не),
• конъюнкция (логическое и),
• дизъюнкция (логическое или),
• импликация (следование),
• эквивалентность (тождество).

Рассмотрим каждую из них подробно. Для описания используем диаграммы Эйлера-Венна и таблицы истинности.

Логическая операция/ соответствие в русском языке	Обозначение	Диаграмма Эйлера-Венна	Таблица истинности
инверсия (отрицание, логическое «НЕ»)/ «…не…», «неверно, что…»	¬		A	¬A
			0	1
			1	0
конъюнкция (логическое «И»)/ «…и…»	Λ, &		A	B	AΛB
			0	0	0
			0	1	0
			1	0	0
			1	1	1
дизъюнкция (логическое «ИЛИ») «…или…», «…либо…»	V		A	B	AVB
			0	0	0
			0	1	1
			1	0	1
			1	1	1
импликация (следование)/ «если…,то…», «когда…, тогда…»	→		A	B	A→B
			0	0	1
			0	1	1
			1	0	0
			1	1	1
эквивалентность (тождество) «тогда и только тогда, когда»	↔, ≡		A	B	A↔B
			0	0	1
			0	1	0
			1	0	0
			1	1	1

Основные логические операции: инверсия, конъюнкция, дизъюнкция.

Остальные логические операции можно выразить через них:

A→B=¬AVB;

A↔B=(AΛB)V(¬AΛ¬B).

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

инверсия, конъюнкция, дизъюнкция, импликация, эквивалентность.

Пример:

AV¬BΛC→D↔E.

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

1. ¬B
2. (¬B)ΛC
3. AV((¬B)ΛC)
4. (AV((¬B)ΛC))→D
5. ((AV((¬B)ΛC))→D)↔E

Перейти к решению задач на алгебру логики из демо ЕГЭ

Математика — Алгебра Логики

Существует 16 = 2²² разных булевых функции с 2 аргументами (обозначим их x и y). Некоторые из них всегда совпадают по значению с булевой константой, булевой переменной или функцией только от одной из двух переменных. Таких функций всего шесть: 0, 1, x, ~x, y, ~y. Далее мы будем из называть тривиальными. Вот таблицы истинности для них:

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

Конъюнкция

Другие названия этой функции: «И», «логическое И», «логическое умножение», «булево умножение». Другие обозначения этой функции: .

Функция «И» дает 1 только когда оба операнда равны 1. Эта функция называется иногда логическим умножением, поскольку ее результаты совпадают с аналогичной операцией в арифметике: 0 * 0 = 0, 0 * 1 = 0, 1 * 0 = 0, 1 * 1 = 1.

Больше

Функция «>» дает 1 только когда первый операнд равен 1, а второй 0. Эта функция не имеет общеупотребительных названий или обозначений. Я обозначил ее символом «>» и назвал «больше» поскольку она равна 1, только когда первый операнд больше второго в арифметическом смысле: 1 > 0.

Меньше

Функция « Сложение по модулю «2»

x	y	xy
0	0	0
0	1	1
1	0	1
1	1	0

Другие названия этой функции: «исключающее ИЛИ», «логическое ЛИБО», «неравносильность», «неэквивалентность», «логическое сложение», «булево сложение».

Другие обозначения этой функции: .

Функция «» дает 1 только когда первый операнд не равен второму операнду. Она похожа на арифметическое сложение: 0 0 = 0, 0 1 = 1, 1 0 = 1, но не всегда: в булевой алгебре 1 1 = 0, а не 2, как в арифметике. Как уже говорилось ранее, булевы величины 1 и 0 не являются числами и для них арифметика неприменима.

Дизъюнкция

x	y	xy
0	0	0
0	1	1
1	0	1
1	1	1

Другие названия этой функции: «ИЛИ», «логическое ИЛИ».

Другие обозначения этой функции:

С обозначением этой функции очень много путаницы. Во-первых, в программировании для нее используется обозначение x|y, но в математике это обозначение уже занято другой логической функцией — штрих Шеффера (см. чуть ниже). Во-вторых, сплошь и рядом для этой функции применяется обозначение «+», но так же часто обозначение «+» применяется для сложения по модулю «2».

Функция «ИЛИ» дает 0 только когда оба операнда равны 0.

Стрелка Пирса

x	y	xy
0	0	1
0	1	0
1	0	0
1	1	0

Другие названия этой функции: «ИЛИ-НЕ».

Эта функция дает 1 только когда оба операнда равны 0.

Равносильность

x	y	xy
0	0	1
0	1	0
1	0	0
1	1	1

Другие названия этой функции: «равносильность».

Другие обозначения этой функции:

Эта функция дает 1 только когда оба операнда равны между собой.

Обратная импликация

x	y	xy
0	0	1
0	1	0
1	0	1
1	1	1

Другие обозначения этой функции:

Эта функция дает 0 только когда первый операнд равен 0, а второй равен 1.

Импликация

x	y	xy
0	0	1
0	1	1
1	0	0
1	1	1

Другие обозначения этой функции:

Эта функция дает 0 только когда первый операнд равен 1, а второй равен 0.

Штрих Шеффера

Другие названия этой функции: «И-НЕ».

Другие обозначения этой функции: ‘ (апостроф).

Эта функция дает 0 только когда оба операнда равны 1.

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

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

Итак, общий формат для обозначения функции от двух аргументов через знак бинарной операции выглядит как (F)#(G), где F и G — некоторые формулы, а # — знак бинарной операции. Для вычисления значения формулы (F)#(G) надо вычислить значение формул F и G, и подставить их в таблицу истинности как первый и второй аргументы функции.

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

Скобки вокруг F можно опускать, если F имеет вид: 0, 1, ~0, ~1, x, ~x, ~(H), где x — произвольная булева переменная, H - произвольная формула булевой алгебры. Иначе скобки опускать нельзя. То же правило относится и к G. Например: (~z & (x & y)) (~(~t & z) & x).

На практике опускают еще больше скобок, если это не затрудняет понимание, и есть договоренность о том, в каком порядке какие операции вычисляются. Обычно первой вычисляется операция «&», потом «» и «», потом все остальные. Если рядом идут операции одного приоритета, то вычисляются подряд слева направо.

Элементы алгебры логики

ЭЛЕМЕНТЫ АЛГЕБРЫ ЛОГИКИ

МАТЕМАТИЧЕСКИЕ ОСНОВЫ ИНФОРМАТИКИ

Ключевые слова

• алгебра логики
• высказывание
• логическая операция
• конъюнкция
• дизъюнкция
• отрицание
• логическое выражение
• таблица истинности
• законы логики

Л огик а

Аристотель (384-322 до н.э.). Основоположник формальной логики (понятие, суждение, умозаключение).

Джордж Буль (1815-1864). Создал новую область науки — Математическую логику (Булеву алгебру или Алгебру высказываний).

Клод Шеннон (1916-2001). Его исследования позволили применить алгебру логики в вычислительной технике

Алгебра

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

Высказывание

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

В русском языке высказывания выражаются повествовательными предложениями:

Земля вращается вокруг Солнца .

Москва — столица.

Но не всякое повествовательное предложение является высказыванием:

Это высказывание ложное.

Побудительные и вопросительные предложения высказываниями не являются.

Без стука не входить!

Откройте учебники.

Ты выучил стихотворение?

Высказывание или нет?

Зимой идет дождь.

Снегири живут в Крыму.

Кто к нам пришел?

У треугольника 5 сторон.

Как пройти в библиотеку?

Переведите число в десятичную систему.

Запишите домашнее задание

• Зимой идет дождь. Снегири живут в Крыму. Кто к нам пришел? У треугольника 5 сторон. Как пройти в библиотеку? Переведите число в десятичную систему. Запишите домашнее задание

Алгебра логики

Алгебра логики определяет правила записи, вычисления значений, упрощения и преобразования высказываний.

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

Если высказывание истинно, то значение соответствующей ему логической переменной обозначают единицей ( А = 1 ), а если ложно — нулём ( В = 0 ).

0 и 1 называются логическими значениями .

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

Высказывания бывают простые и сложные.

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

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

Название логической операции

Конъюнкция

Логическая связка

Дизъюнкция

«и»; «а»; «но»; «хотя»

«или»

Инверсия

«не»; «неверно, что»

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

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

Другое название: логическое умножение.

Обозначения:  ,  , & , И.

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

Графическое представление

А

0

В

А & В

0

0

0

1

1

1

0

0

0

1

1

A

B

А&В

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

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

Другое название: логическое сложение .

Обозначения: V, |, ИЛИ, +.

Графическое представление

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

А

0

В

А V В

0

0

0

1

1

1

0

1

1

1

1

A

B

АVВ

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

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

Другое название: логическое отрицание.

Обозначения: НЕ, ¬ , ¯ .

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

Графическое представление

А

0

Ā

1

1

0

A

Ā

Логические операции имеют следующий приоритет:

инверсия, конъюнкция, дизъюнкция .

Логика и обозначение множеств

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

Логика высказываний

Предложение — это декларативное утверждение, которое либо истинно, либо ложно. Если предложение истинно, то мы говорим, что оно имеет истинностное значение true. Соответственно, если предложение ложно, его истинностное значение ложно.2} \) также четное.

Примеры ложных предложений:

• Электрон тяжелее протона;
• \ (1 + 2 \ gt 3; \)
• \ (6 \) — простое число.

Не все предложения являются предложениями:

• \ (x \ gt 5 \) (Это может быть истина или ложь в зависимости от \ (x \))
• Идёт дождь? (Это вопрос, а не декларативное предложение)
• Картины Мондриана слишком абстрактны. (Что абстрактного и слишком абстрактного?)

Для обозначения предложений мы обозначаем их буквами.Самые распространенные буквы: \ (p, \) \ (q, \) \ (r, \) \ (s, \) \ (t. \)

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

Логические операторы и таблицы истинности

Пусть \ (p \) и \ (q \) — два предложения. Каждое из этих утверждений может принимать два значения — истина (\ (T \)) и ложь (\ (F \)). Итак, есть \ (4 \) пары входных значений: \ (TT, \) \ (TF, \) \ (FT, \) и \ (FF. \)

Предположим, что новое предложение \ (r \) составлено из \ (p \) и \ (q. \). Значения истинности предложения \ (r \) могут принимать разные значения (\ (T \) или \ ( F \)) для каждой пары входных значений.4 = 16 \) возможных выходных комбинаций (функций истинности) для \ (2 \) двоичных входных переменных. Каждая из этих комбинаций представлена ​​определенным логическим оператором.

Далее мы рассмотрим наиболее важных операторов.

Отрицание

Отрицание — унарный логический оператор. Если \ (p \) — предложение, то отрицание \ (p \) называется not \ (p \) и обозначается \ (\ lnot p. \)

.

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

В случае оператора отрицания таблица истинности очень проста:

Как видите, оператор логического отрицания меняет значение истинности входного предложения.

Пример 1 :

\ (п: \)	Трапеция четырехугольник (истинный)
\ (\ lnot p: \)	Трапеция не четырехугольник (ложь)

Пример 2 :

\ (п: \)	\ (2 \) — простое число (правда)
\ (\ lnot p: \)	\ (2 \) не является простым числом (ложь)

Рассмотрим теперь несколько бинарных операторов.

Соединение

Если \ (p \) и \ (q \) — два предложения, то их соединение означает \ (p \) и \ (q \) и обозначается \ (p \ land q. \)

Конъюнкция \ (p \ land q \) истинна только тогда, когда оба \ (p \) и \ (q \) истинны. В противном случае это ложь. Таким образом, таблица истинности конъюнкции выглядит следующим образом:

Пример 1 :

\ (п: \)	Соединенное Королевство является членом Европейского Союза (неверно)
\ (q: \)	Ирландия является членом Европейского Союза (правда)
\ (п \ земля q: \)	Соединенное Королевство и Ирландия являются членами Европейского Союза (неверно)

Пример 2 :

\ (п: \)	\ (3 \) простое (истинное)
\ (q: \)	\ (3 \) нечетное (правда)
\ (п \ земля q: \)	\ (3 \) простое и нечетное (истинное)

Дизъюнкция

Если \ (p \) и \ (q \) — два предложения, то их дизъюнкция означает \ (p \) или \ (q \) и обозначается \ (p \ lor q.\)

Дизъюнкция \ (p \ lor q \) истинна, когда либо \ (p \) истинно, \ (q \) истинно, либо оба истинны. Это неверно, если оба \ (p \) и \ (q \) ложны.

Таблица истинности дизъюнкции:

Пример 1 :

\ (п: \)	Протон имеет отрицательный заряд (ложно)
\ (q: \)	Нейтрон имеет отрицательный заряд (ложный)
\ (p \ lor q: \)	Протон или нейтрон имеют отрицательный заряд (ложный)

Пример 2 :

\ (п: \)	\ (\ large {\ frac {2} {3}} \ normalsize \) — рациональное число (верно)
\ (q: \)	\ (\ large {\ frac {\ sqrt {2}} {5}} \ normalsize \) — рациональное число (ложь)
\ (p \ lor q: \)	Либо \ (\ large {\ frac {2} {3}} \ normalsize \), либо \ (\ large {\ frac {\ sqrt {2}} {5}} \ normalsize \), либо оба числа являются рациональными ( правда)

Материал условный

Материальное условие для \ (p \) и \ (q \) означает утверждение, если \ (p \), то \ (q \), и обозначается как \ (p \ to q.\) Этот логический оператор также называется условным оператором.

Если \ (p \) истинно, то условное \ (p \ to q \) принимает значение истинности \ (q. \). Если \ (p \) ложно, то условное \ (p \ to q \) по умолчанию считается истинным.

Вот таблица истинности условного оператора:

Условное выражение \ (p \ to q \) может быть выражено разными предложениями, некоторые из них перечислены ниже:

• \ (p \) означает \ (q \)
• \ (p \) является достаточным условием для \ (q \)
• \ (q \) — необходимое условие для \ (p \)
• \ (q \) следует из \ (p \)
• \ (p \) только если \ (q \)

Пример :

\ (п: \)	\ (x \) делится на \ (2 \) и \ (3 \)
\ (q: \)	\ (x \) делится на \ (6 \)
\ (от p \ к q: \)	Если \ (x \) делится на \ (2 \) и \ (3, \), то \ (x \) делится на \ (6.\)
\ (х = 12: \)	\ (p \) истинно, \ (q \) истинно, и \ (p \ to q \) истинно.
\ (х = 13: \)	\ (p \) ложно, \ (q \) ложно, а \ (p \ to q \) верно.

Специальные условные предложения

• Обратным к \ (p \ к q \) является предложение \ (q \ to p \)
• Противоположностью \ (p \ to q \) является предложение \ (\ neg q \ to \ neg p \)
• Обратным к \ (p \ to q \) является предложение \ (\ neg p \ to \ neg q \)

Если утверждение \ (p \ to q \) верно, то верно и противоположное.Если верно обратное, то верно и обратное.

Специальные условные операторы определяются следующей таблицей истинности:

Пример :

Выражение \ (p \)

Четырехугольник — это прямоугольник (ложь)

Выражение \ (q \)

Сумма внутренних углов четырехугольника равна \ (360 \) градусов (правда).

Условное выражение \ (p \ to q \)

Если четырехугольник является прямоугольником, то сумма его внутренних углов равна \ (360 \) градусам (истинно).

Преобразование \ (p \ to q: \) \ (q \ to p \)

Если сумма внутренних углов четырехугольника равна \ (360 \) градусов, то это прямоугольник ( ложный).

Обратно \ (p \ to q: \) \ (\ neg p \ to \ neg q \)

Если четырехугольник не является прямоугольником, то сумма его внутренних углов не равна \ (360 \) градусов (ложь).

Противоположность \ (p \ to q: \) \ (\ neg q \ to \ neg p \)

Если сумма внутренних углов четырехугольника не равна \ (360 \) градусам, то это не прямоугольник (правда).

Материал Biconditional

Материальное биконусное или логическое биконусное выражение \ (p \) и \ (q \) означает утверждение \ (p \) тогда и только тогда, когда \ (q \) и обозначается \ (p \ leftrightarrow q. \)

Двухусловный оператор имеет то же значение истинности, что и составной логический оператор \ (\ left ({p \ to q} \ right) \ land \ left ({q \ to p} \ right), \), что означает \ (p \) влечет \ (q \), а \ (q \) влечет \ (p. \)

Таблица истинности для двусмысленного утверждения имеет вид

Пример 1 :

\ (п: \)	Три вектора компланарны (истинно)
\ (q: \)	Скалярное тройное произведение трех векторов равно нулю (истина)
\ (p \ leftrightarrow q: \)	Три вектора компланарны тогда и только тогда, когда их тройное скалярное произведение равно нулю (истина)

Пример 2 :

\ (п: \)	Теннисный матч будет проводиться на открытом воздухе (ложь)
\ (q: \)	Идёт дождь (правда)
\ (p \ leftrightarrow q: \)	Теннисный матч будет проводиться на открытом воздухе только в том случае, если идет дождь (ложь)

Логическая эквивалентность

Утверждения \ (p \) и \ (q \) называются логически эквивалентными, если они имеют одинаковые таблицы истинности.Логическая эквивалентность \ (p \) и \ (q \) обозначается как \ (p \ Equiv q, \) или иногда как \ (\ Leftrightarrow \) в зависимости от используемых обозначений.

Предикаты и квантификаторы

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

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

Предикат — это логический оператор, содержащий одну или несколько переменных или параметров. Предикаты обозначаются заглавной буквой, а переменные указываются в качестве аргументов, например \ (P \ left (x \ right) \) или \ (Q \ left ({x, y} \ right).\) Значение истинности предиката зависит от значений его переменных.

Пример 1 :

Предикат \ (P \ left (x \ right) \)
\ (P \ left (x \ right): \) \ (x \) — это планета
\ (x \ ) = Венера	Истинное предположение
\ (P \ left (\ text {Venus} \ right): \) Венера — планета
\ (x \) = Антарес	Ложное утверждение
\ (P \ left (\ text {Antares} \ right): \) Антарес — это планета

Пример 2 :

Предикат \ (Q \ left ({x, y} \ right) \)
\ (Q \ left ({x, y} \ right): {x ^ 2} + {y ^ 2 } \ le 4 \)
\ (x = 1, y = -1 \)	Истинное предложение
\ (Q \ left ({1, -1} \ right): {1 ^ 2 } + {\ left ({- 1} \ right) ^ 2} \ le 4 \)
\ (x = 1, y = 2 \)	Ложное утверждение
\ (Q \ left ( {1,2} \ right): {1 ^ 2} + {2 ^ 2} \ le 4 \)

Подобно суждениям, предикат принимает два значения — истина или ложь.Следовательно, к ним применимы все операции логической алгебры. Используя операторы \ (\ neg, \ land, \ lor, \ rightarrow, \) и \ (\ leftrightarrow, \), мы можем формировать более сложные предикаты.

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

В логике предикатов есть два типа кванторов — универсальный квантор и квантор существования.

Универсальный квантификатор

Универсальный квантификатор используется для выражения предложений такими словами, как все или каждый. Он обозначается символом \ (\ forall. \). Обозначение \ (\ forall x P \ left ({x} \ right) \) означает «для каждого значения \ (x \) в определенной области предикат \ (P \ left ({x} \ right) \) верно ». Область называется универсумом дискурса или областью дискурса.

Экзистенциальный квантификатор

Квантификатор существования используется для выражения предложений такими словами, как some или there is.Он обозначается символом \ (\ существует. \) Обозначение \ (\ exists x P \ left ({x} \ right) \) означает, что «существует некоторое значение \ (x \) такое, что \ (P \ left ({x} \ right) \) верно ».

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

Обозначение конструктора множеств

Нотация построителя множеств используется для определения набора объектов с помощью предиката. Обычная нотация включает части \ (3 \): переменную \ (x, \), разделитель двоеточия или вертикальной черты и логический предикат \ (P \ left ({x} \ right): \)

\ [S = \ left \ {{x | P \ left (x \ right)} \ right \}, \]

где \ (S \) обозначает множество объектов.

Единственная переменная \ (x \) может быть заменена термином, который может включать одну или несколько переменных в сочетании с функциями, действующими на них. Предикат \ ({P \ left (x \ right)} \) может быть представлен сложной логической формулой.

Некоторые другие определения и обозначения

\ (\ {\; \} \)	— это набор
\ (x \ дюйм S \)	\ (x \) является элементом или членом \ (S \)
\ (x \ notin S \)	\ (x \) не является элементом \ (S \)
\ (S \ Subteq T \)	\ (S \) является подмножеством \ (T \)
\ (S = T \)	эквивалентно \ (\ left ({S \ substeq T} \ right) \ land \ left ({T \ substeq S} \ right) \)
\ (S \ подмножество T \)	\ (S \) является собственным подмножеством \ (T.\) Это означает \ (\ left ({S \ substeq T} \ right) \ land \ left ({T \ ne S} \ right) \)
\ (\ require {AMSsymbols} \ varnothing \)	пустой набор

---

Решенные проблемы

Щелкните или коснитесь проблемы, чтобы увидеть решение.

Пример 1

Докажите законы Де Моргана: \ [\ neg \ left ({p \ land q} \ right) \ Equiv \ left ({\ neg p} \ right) \ lor \ left ({\ neg q} \ right), \] \ [\ neg \ left ({p \ lor q} \ right) \ Equiv \ left ({\ neg p} \ right) \ land \ left ({\ neg q} \ right).\]

Пример 2

Покажите, что заявление \ [s = \ left ({p \ lor \ neg q} \ right) \ lor \ left ({\ neg p \ land q} \ right) \] это тавтология.

Пример 3

Покажите, что заявление \ [r = (\ neg p \ land q) \ land (p \ leftrightarrow q) \] противоречие.

Пример 4

Докажите закон распределения \ [p \ lor \ left ({q \ land r} \ right) \ Equiv \ left ({p \ lor q} \ right) \ land \ left ({p \ lor r} \ right). \]

Пример 5

Пусть \ (G \ left ({x, y} \ right) \) будет предикатом «\ (x \) ходит в спортзал \ (y \) раз в неделю.”Запишите следующие предложения в записи предикатов:

1. Ник ходит в спортзал \ (4 \) раза в неделю.
2. Николь ходит в спортзал \ (2 \) или \ (3 \) раза в неделю.
3. Макс ходит в спортзал 2 раза в неделю, но не каждую неделю.
4. Эми иногда ходит в спортзал.
5. Некоторые люди ходят в спортзал каждый день.
6. Вряд ли кто-нибудь ходит в спортзал 15 раз в неделю.

Пример 6

Предположим, \ (x \) — студент, \ (y \) — курс математики, а \ (M \ left ({x, y} \ right) \) — предикат «\ (x \) примет \ ( у \) ».Переведите следующие предложения в предикатную нотацию:

1. Каждый студент будет изучать математический анализ.
2. Каждый студент будет изучать математику.
3. Лора будет изучать математику и линейную алгебру.
4. Есть курс, который пройдут все.
5. Есть курс, на который никто не пойдет.
6. Том будет изучать все курсы математики, кроме топологии.

Пример 7

Опишите следующие наборы, используя нотацию построителя наборов:

1. \ (\ left \ {{- 27, — 8, — 1,0,1,8,27} \ right \} \)
2. \ (\ left \ {{\ large {\ frac {1} {2}} \ normalsize, \ large {\ frac {2} {3}} \ normalsize, \ large {\ frac {3} {4}} \ normalsize, \ large {\ frac {4} {5}} \ normalsize, \ large {\ frac {5} {6}} \ normalsize} \ right \} \)
3. \ (\ left \ {{5,8,13,21,34,55} \ right \} \)

Пример 1.

Докажите законы Де Моргана: \ [\ neg \ left ({p \ land q} \ right) \ Equiv \ left ({\ neg p} \ right) \ lor \ left ({\ neg q} \ right), \] \ [\ neg \ left ({p \ lor q} \ right) \ Equiv \ left ({\ neg p} \ right) \ land \ left ({\ neg q} \ right). \]

Решение.

Мы проверяем \ (1 \ text {st} \) закон Де Моргана, используя таблицу истинности.

Сначала запишем все возможные комбинации предложений \ (p \) и \ (q. \). Отрицания \ (p \) и \ (q \) являются их противоположными значениями. Выражение \ (p \ land q \) является конъюнкцией \ (p \) и \ (q.\) Затем определяем отрицание конъюнкции \ (\ neg \ left ({p \ land q} \ right) \). Выражение \ (\ left ({\ neg p} \ right) \ lor \ left ({\ neg q} \ right) \) является дизъюнкцией \ (\ neg p \) и \ (\ neg q. \)

1-й закон Де Моргана

Мы видим, что два последних столбца таблицы истинности совпадают. Это доказывает \ (1 \ text {st} \) закон Де Моргана.

Аналогичным образом мы можем проверить \ (2 \ text {nd} \) закон Де Моргана:

2-й закон Де Моргана

Пример 2.

Покажите, что заявление \ [s = \ left ({p \ lor \ neg q} \ right) \ lor \ left ({\ neg p \ land q} \ right) \] это тавтология.

Решение.

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

Значения \ (p, \) \ (q, \) \ (\ neg p, \) и \ (\ neg q \) легко заполнить. Следующий столбец \ ({p \ lor \ neg q } \) означает дизъюнкцию \ (p \) и \ (\ neg q. \). Затем мы находим конъюнкцию \ ({\ neg p \ land q}. \) Последнее утверждение \ (s \) является дизъюнкцией двух предыдущих предложения.

Утверждение тавтологии

Мы видим, что все значения \ (4 \) в последнем столбце верны.Следовательно, утверждение \ (s = \ left ({p \ lor \ neg q} \ right) \ lor \ left ({\ neg p \ land q} \ right) \) является тавтологией.

Пример 3.

Покажите, что заявление \ [r = (\ neg p \ land q) \ land (p \ leftrightarrow q) \] противоречие.

Решение.

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

Первое выражение \ (\ neg p \ land q \) является соединением \ (\ neg p \) и \ (q.\) Второе выражение \ (p \ leftrightarrow q \) является двойным условием для \ (p \) и \ (q \). Последняя операция — это соединение двух предыдущих предложений.

Заявление о противоречии

Последний столбец содержит только ложные значения. Следовательно, утверждение \ (r = (\ neg p \ land q) \ land (p \ leftrightarrow q) \) противоречит.

Пример 4.

Докажите закон распределения \ [p \ lor \ left ({q \ land r} \ right) \ Equiv \ left ({p \ lor q} \ right) \ land \ left ({p \ lor r} \ right).\]

Решение.

Мы строим таблицу истинности, чтобы убедиться, что левая и правая части утверждения эквивалентны.

Обозначим

\ [{s1 = p \ lor \ left ({q \ land r} \ right), \; \;} \ kern0pt {s2 = \ left ({p \ lor q} \ right) \ land \ left ({ p \ lor r} \ right)} \]

и найдите значения истинности \ (s1 \) и \ (s2. \)

Применяя операции конъюнкции и дизъюнкции, получаем следующую таблицу:

Распределительный закон

Последние два столбца таблицы идентичны.Это означает, что

\ [{s1 \ Equiv s2,} \; \; \ Rightarrow {p \ lor \ left ({q \ land r} \ right) \ Equiv \ left ({p \ lor q} \ right) \ land \ left ({p \ lor r} \ right).} \]

Пример 5.

Пусть \ (G \ left ({x, y} \ right) \) будет предикатом «\ (x \) ходит в спортзал \ (y \) раз в неделю». Запишите следующие предложения в записи предикатов:

1. Ник ходит в спортзал \ (4 \) раза в неделю.
2. Николь ходит в спортзал \ (2 \) или \ (3 \) раза в неделю.
3. Макс ходит в спортзал 2 раза в неделю, но не каждую неделю.
4. Эми иногда ходит в спортзал.
5. Некоторые люди ходят в спортзал каждый день.
6. Вряд ли кто-нибудь ходит в спортзал 15 раз в неделю.

Решение.

1. Ник ходит в спортзал \ (4 \) раза в неделю.
\ [G \ left ({Nick, 4} \ right) \]
2. Николь ходит в спортзал \ (2 \) или \ (3 \) раза в неделю.
\ [G \ left ({Николь, 2} \ right) \ lor G \ left ({Николь, 3} \ right) \]
3. Макс ходит в спортзал 2 раза в неделю, но не каждую неделю.
\ [G \ left ({Max, 2} \ right) \ lor G \ left ({Max, 0} \ right) \]
4. Эми иногда ходит в спортзал.
\ [\ существует y G \ left ({Amy, y} \ right) \]
5. Некоторые люди ходят в спортзал каждый день.
\ [\ существует x G \ left ({x, 7} \ right) \]
6. Вряд ли кто-нибудь ходит в спортзал 15 раз в неделю.
\ [\ neg \ существует x G \ left ({x, 15} \ right) \]

Пример 6.

Предположим, \ (x \) — студент, \ (y \) — курс математики, а \ (M \ left ({x, y} \ right) \) — предикат «\ (x \) примет \ ( у \) ». Переведите следующие предложения в предикатную нотацию:

1. Каждый студент будет изучать математический анализ.
2. Каждый студент будет изучать математику.
3. Лора будет изучать математику и линейную алгебру.
4. Есть курс, который пройдут все.
5. Есть курс, на который никто не пойдет.
6. Том будет изучать все курсы математики, кроме топологии.

Решение.

1. Каждый студент будет изучать математический анализ.
\ [\ forall x M \ left ({x, Calculus} \ right) \]
2. Каждый студент будет изучать математику.
\ [\ forall x \ существует yM \ left ({x, y} \ right) \]
3. Лора будет изучать математику и линейную алгебру.
\ [M \ left ({Лора, Исчисление} \ right) \ land M \ left ({Лора, Линейная алгебра} \ right) \]
4. Есть курс, который пройдут все.
\ [\ существует y \ forall xM \ left ({x, y} \ right) \]
5. Есть курс, на который никто не пойдет.
\ [\ существует y \ forall x \ neg M \ left ({x, y} \ right) \]
6. Том будет изучать все курсы математики, кроме топологии.
\ [\ forall yM \ left ({Tom, y} \ right) \ land \ neg M \ left ({Tom, Topology} \ right) \]

Пример 7.

Опишите следующие наборы, используя нотацию построителя наборов:

1. \ (\ left \ {{- 27, — 8, — 1,0,1,8,27} \ right \} \)
2. \ (\ left \ {{\ large {\ frac {1} {2}} \ normalsize, \ large {\ frac {2} {3}} \ normalsize, \ large {\ frac {3} {4}} \ normalsize, \ large {\ frac {4} {5}} \ normalsize, \ large {\ frac {5} {6}} \ normalsize} \ right \} \)
3. \ (\ left \ {{5,8,13,21,34,55} \ right \} \)

Решение.3} \ text {and} — 3 \ le x \ le 3} \ right \} \]

Множество \ (\ left \ {{\ large {\ frac {1} {2}} \ normalsize, \ large {\ frac {2} {3}} \ normalsize, \ large {\ frac {3} {4} }} \ normalsize, \ large {\ frac {4} {5}} \ normalsize, \ large {\ frac {5} {6}} \ normalsize} \ right \} \) содержит дроби, знаменатель которых больше его числитель равен \ (1 \), а числитель находится в диапазоне от \ (1 \) до \ (5. \)

\ [\ left \ {{x \ in \ mathbb {N} \, | \, \ frac {x} {{x + 1}} \ text {and} 1 \ le x \ le 5} \ right \} \ ]

Набор \ (\ left \ {{5,8,13,21,34,55} \ right \} \) является частью последовательности Фибоначчи \ ({F_n} \) из \ (n = 6 \) к \ (n = 11.\)

\ [{\ left \ {{x \ in \ mathbb {N} \, | \, x \ in {F_n},} \ right.} \ kern0pt {\ left. {\ text {where} n \ in \ mathbb {N} \ text {и} 6 \ le n \ le 11} \ right \}} \]

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

Математика обычно включает сочетание истинных (или гипотетически истинных) утверждения различными способами для создания (или доказательства) новых истинных утверждений. 2 + y = 12 $», то $ P (2,8) $ и $ P (3,3) $ равны истина, а $ P (1,4) $ и $ P (0,6) $ — ложь.Если $ Q (x, y, z) $ равно «$ x + y

Верно ли предложение или ложно, обычно зависит от того, что мы о чем говорят — одно и то же предложение может быть верным или ложным в зависимости от по контексту; например, формула $ x | y $ означает `$ x $ делит $ y $ ‘. То есть $ x | y $, если есть некоторый $ z $, так что $ y = x \ cdot z $. Сейчас же, правда ли, что $ 3 | 2 $? Это зависит: если мы говорим о целых числах, ответ — нет; если мы говорим о рациональных числах, ответ да, потому что $ 2 = 3 \ cdot (2/3) $. (Конечно, если $ x \ not = 0 $ и $ y $ любых рациональных чисел, затем $ x | y $, так что это не очень полезное понятие.При нормальном использовании вид формулы «$ x | y $» означает , что $ x $ и $ y $ являются целыми числами.)

Вселенная дискурса для определенной области математики — это набор, который содержит все интересное по этой теме. Когда мы изучение математических формул типа `$ x $ делит $ y $ ‘на переменные Предполагается, что принимают значения в любой вселенной дискурса подходит для конкретной темы. Вселенная дискурса обычно это ясно из обсуждения, но иногда нам нужно определите это явно для ясности.Универсум дискурса обычно обозначается $ U $.

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

Если $ P $ — формула, то «not $ P $» — другое формула, которую мы символически записываем как $ \ lnot P $. Конечно, $ \ lnot P $ ложно, если $ P $ истинно, и наоборот — например,

«6 — не простое число» или «Неверно, что 6 — это простое число. премьер » или «$ \ lnot (\ hbox {6 простое число}) $ » (T)

«Рональд Рейган не был президентом.» (F)

Предположим, что $ P $ и $ Q $ — формулы. Затем «$ P $ и $ Q $» — это формула, записанная символически. как $ P \ land Q $, называемое конъюнкцией $ P $ и $ Q $. Чтобы $ P \ land Q $ выполнялись как $ P $, так и $ Q $ должно быть истинным, в противном случае — ложным, например,

«5 долларов = 6 долларов и 7 долларов = 8 долларов». (F)

«Сиэтл находится в Вашингтоне, а Бойсе — в Айдахо». (T)

«Толстой был русским, а Диккенс — Французский ». (F)

Если $ P $ и $ Q $ являются формулами, то формула «$ P $ или $ Q $» символически записывается как $ P \ lor Q $, называемая дизъюнкция $ P $ и $ Q $.это важно отметить, что это включительно или, то есть «либо или оба». Итак, если $ P $, $ Q $ или и $ P $ и $ Q $ верны, так и $ P \ lor Q $. Единственный способ, которым $ P \ lor Q $ может быть ложным, — это если оба $ P $ и $ Q $ ложны — например,

«Вашингтон находится в Канаде, а Лондон — в Англии». (T)

«$ 5

«Ленин был испанцем или Ганди был итальянцем». (F)

Если $ P $ и $ Q $ — формулы, то «если $ P $, то $ Q $» или написано «$ P $ подразумевает $ Q $» $ P \ подразумевает Q $, используя условный символ , $ \ подразумевает $.Не очевидно (по крайней мере, для большинства людей), при каких условиях обстоятельства $ P \ подразумевают, что Q $ должно быть истинным. Отчасти это потому, что «if… then» используется более чем одним способом в обычном английском языке, однако нам нужно исправить правило, которое позволит нам точно знать, когда $ P \ подразумевает Q $ верно. Конечно, если $ P $ истинно, а $ Q $ ложно, $ P $ не может следует $ Q $, поэтому $ P \ означает, что Q $ в этом случае неверно. Чтобы помочь нам с в остальных случаях рассмотрим следующее утверждение:

«Если $ x $ меньше 2, тогда $ x $ меньше 4.»

Это утверждение должно быть верным независимо от значения $ x $. (при условии, что вселенная дискурса является чем-то знакомым, например целые числа). Если $ x $ равен 1, он оценивается как $ \ rm T \ implies T $, если $ x $ равно 3, оно становится $ \ rm F \ Impies T $, а если $ x $ равно 5, оно становится $ \ rm F \ влечет F $. Получается, что $ P \ подразумевает, что Q $ истинно, если $ P $ истинно, а $ Q $ ложно. Это правило, которое мы принимаем.

Наконец, двояковыпук , записанный $ \ Leftrightarrow $, соответствует фраза «тогда и только тогда» или «если и только если» кратко.Итак, $ P \ Leftrightarrow Q $ истинно, когда и $ P $, и $ Q $ имеют то же значение истинности, в противном случае — ложь.

Пример 1.1.2. Предположим, что $ P (x, y) $ — это «$ x + y = 2 $», а $ Q (x, y) $ равно «$ xy> 1 $». Тогда, когда $ x = 1 $ и $ y = 1 $, $ \ lnot P (x, y) $, $ P (x, y) \ land Q (x, y) $, $ P (x, y) \ lor Q (x, y) $, $ P (x, y) \ влечет Q (x, y) $ и $ P (x, y) \ Leftrightarrow Q (x, y) $ имеют значения истинности F, F, T, F, F, соответственно, и когда $ x = 2 $ и $ y = 3 $ имеют значения истинности T, F, T, T, F соответственно. $ \ квадрат $

Используя операции $ \ lnot $, $ \ land $, $ \ lor $, $ \ implies $, $ \ Leftrightarrow $, мы можем построить составных выражений, таких как $$ (P \ land (\ lnot Q)) \ подразумевает ((\ lnot R) \ lor ((\ lnot P) \ land Q)).$$ Как показывает этот пример, иногда необходимо включать много круглых скобок, чтобы сгруппировать термины в формуле ясно. Как и в алгебре, где умножение имеет приоритет перед сложением, мы можем убрать скобки согласование определенного порядка, в котором логические операции выполняются. Мы будет применять операции в этом порядке, начиная с от начала до конца: $ \ lnot $, $ \ land $, $ \ lor $, $ \ подразумевает $ и $ \ Leftrightarrow $. Так $$ A \ подразумевает B \ lor C \ land \ lnot D $$ это сокращение от $$ A \ подразумевает (B \ lor (C \ land (\ lnot D))).$$ Как и в алгебре, часто имеет смысл включить несколько дополнительных круглых скобок, чтобы убедиться, что предполагаемое значение ясно. Большая часть информации, которую мы обсудили, может быть обобщена в таблицах истинности . Например, таблица истинности для $ \ lnot P $:

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

$ P $	$ Q $	$ P \ land Q $	$ P \ lor Q $	$ P \ Rightarrow Q $	$ P \ Leftrightarrow Q $
T	T	T	T	T	T
F	T	F	T	T	F
T	F	F	T	F	F
F	F	F	F	T	T

У любого составного выражения есть таблица истинности.n $ строк в таблице, потому что есть много разных способов назначить Команды T и F для простых формул $ n $ в составном выражении. Таблица истинности для $ (P \ land Q) \ lor \ lnot R $:

$ P \ land Q $

$ P $	$ Q $	$	$ \ lnot R $	$ (P \ land Q) \ lor \ lnot R $
T	T	T	T	F	T
F	T	T	F	F	F
T	F	T	F	F	F
F	F	T	F	F	F
T	T	F	T	T	T
F	T	F	F	T	T
T	F	F	F	T	T
F	F	F	F	T	T

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

Тавтология — это логическое выражение, которое всегда оценивается как T, то есть последний столбец его таблицы истинности состоит только из Т. Иногда говорят, что тавтология действительна ; хотя «действительный» используется в других контекстах как что ж, это не должно вызывать путаницы. Например, $ (P \ land Q) \ lor P \ Leftrightarrow P $ — тавтология, поскольку ее таблица истинности:

$ P $	$ Q $	$ P \ land Q $	$ (P \ land Q) \ lor P $	$ (P \ land Q) \ lor P \ Leftrightarrow P $
T	T	T	T	T
F	T	F	F	T
T	F	F	T	T
F	F	F	F	T

Мы перечислим несколько важных тавтологий в следующей теореме.

Теорема 1.1.3 Справедливы следующие утверждения.

а) $ P \ Leftrightarrow \ lnot \ lnot P $

б) $ P \ lor Q \ Leftrightarrow Q \ lor P $

c) $ P \ land Q \ Leftrightarrow Q \ land P $

d) $ (P \ land Q) \ land R \ Leftrightarrow P \ land (Q \ land R) $

e) $ (P \ lor Q) \ lor R \ Leftrightarrow P \ lor (Q \ lor R) $

f) $ P \ land (Q \ lor R) \ Leftrightarrow (P \ земля Q) \ lor (P \ land R) $

г) $ P \ lor (Q \ land R) \ Leftrightarrow (P \ lor Q) \ land (P \ lor R) $

ч) $ (P \ подразумевает Q) \ Leftrightarrow (\ lnot P \ lor Q) $

i) $ P \ влечет (P \ lor Q) $

j) $ P \ land Q \ подразумевает Q $

k) $ (P \ Leftrightarrow Q) \ Leftrightarrow ((P \ подразумевает Q) \ land (Q \ влечет P)) $

l) $ (P \ подразумевает Q) \ Leftrightarrow (\ lnot Q \ подразумевает \ lnot P) $

Доказательство. Доказательства оставлены как упражнения. $ \ qed $

Заметим, что (b) и (c) — коммутативные законы, (d) и (e) — ассоциативные законы и (f) и (g) говорят, что $ \ land $ и $ \ lor $ распределяются друг над другом. Это говорит о том, что существует форма алгебры для логических выражений, аналогичных алгебре для числовых выражений. Этот предмет называется булевой алгеброй и имеет множество применений, особенно в информатике.

Если две формулы всегда принимают одно и то же значение истинности, несмотря ни на что элементы из вселенной дискурса мы заменяем различными переменных, тогда мы говорим, что они эквивалентны .Стоимость эквивалента формулы в том, что они говорят одно и то же. Это всегда правильный шаг в доказательстве заменить некоторую формулу на эквивалентную. Кроме того, многие тавтологии содержат важные идеи для построения доказательств. Для Например, (k) говорит, что если вы хотите показать, что $ P \ Leftrightarrow Q $, это возможно (и часто желательно) разбить доказательство на два частей, одна из которых доказывает, что из $ P \ следует Q $, а вторая Доказывая обратное , из $ Q \ следует P $.

Читая теорему 1.1.3 у вас может быть заметил, что $ \ land $ и $ \ lor $ удовлетворяют многим аналогичным свойствам. Они называются «двойственными» понятиями — для любого свойства один, есть почти идентичное свойство, которому удовлетворяет другой, при этом экземпляры двух операций поменялись местами. Это часто означает, что когда мы доказываем результат, включающий одно понятие, мы получаем соответствующий результат для его дуала без дополнительной работы.

Джордж Буль. логический (1815–1864) имел только общее школьное образование, хотя учился Греческий и латинский сами по себе.Он начал свою карьеру элементарным школьный учитель, но решил, что ему нужно больше узнать о математике, поэтому он начал изучать математику, а также языки, необходимые для чтения современной литературы на математика. В 1847 году он опубликовал небольшую книгу The Mathematical Анализ логики , который справедливо можно сказать, положил начало исследованию математической логики. Ключевой вклад работы был в новое определение «математики», чтобы не означать просто «изучение чисел и величина », но изучение символов и манипуляции с ними в соответствии с к определенным правилам.Важность этого уровня абстракции для будущее математики трудно переоценить. Наверное, на Благодаря этой работе он перешел на работу в Куинс-колледж в Корке.

В Исследование законов мышления , опубликованном в 1854 году, Буль установил настоящую формальную логику, развивая то, что сегодня называется Булева алгебра или иногда алгебра множеств . Он использовал символы для сложение и умножение как операторы, но полностью абстрактно смысл.Сегодня эти символы все еще иногда используются в логических алгебры, хотя символы `$ \ land $ ‘и` $ \ lor $’, `$ \ cap $ ‘и Также используются `$ \ cup $ ‘. Бул применил алгебраические манипуляции к процесс рассуждения. Вот простой пример такого рода манипуляции, которые он совершил: уравнение $ xy = x $ (которое сегодня можно было бы записать $ x \ land y = x $ или $ x \ cap y = x $) означает, что `все, что удовлетворяет $ x $ удовлетворяет $ y $ ‘или, в наших терминах, $ x \ влечет y $. Если также $ yz = y $ (что есть, $ y \ подразумевает z $), то замена $ y = yz $ на $ xy = x $ дает $ x (yz) = x $ или $ (xy) z = x $.2 + bD + c = 0 $, лечение $ D $ как номер предоставляет информацию о решениях для дифференциальное уравнение.

Информация здесь взята из A History of Mathematics, by Карл Б. Бойер, Нью-Йорк: Джон Вили и сыновья, 1968. Подробнее информацию см. Лекции о десяти британских математиках , автор: Александр Макфарлейн, Нью-Йорк: John Wiley & Sons, 1916.

Упражнения 1.1

Пример 1.1.1 Постройте таблицы истинности для следующих логических выражений:

а) $ (P \ land Q) \ lor \ lnot P $

б) $ P \ подразумевает (Q \ land P) $

c) $ (P \ land Q) \ Leftrightarrow (P \ lor \ lnot R) $

d) $ \ lnot P \ подразумевает \ lnot (Q \ lor R) $

Пр. 1.1,2 Проверьте тавтологии теоремы 1.1.3.

Пример 1.1.3 Предположим, что $ P (x, y) $ — это формула «$ x + y = 4 $», а $ Q (x, y) $ — это формула «$ x

$ P (x, y) \ land Q (x, y) $, $ \ lnot P (x, y) \ lor Q (x, y) $,

$ P (x, y) \ влечет \ lnot Q (x, y) $, $ \ lnot (P (x, y) \ Leftrightarrow Q (x, y)) $,

используя значения:

a) x = 1, y = 3

c) x = 1, y = 2

b) x = 3, y = 1

d) $ x = 2, y = 1 $

Пр. 1.1,4

а) Найдите таблицы истинности для $$ P \ land (\ lnot Q) \ land R, \ quad \ quad (\ lnot P) \ land Q \ land (\ lnot R) $$

б) Используйте их, чтобы найти таблицу истинности для $$ (P \ земля (\ lnot Q) \ земля R) \ lor ((\ lnot P) \ land Q \ land (\ lnot R)) $$

c) Используйте метод, предложенный в частях (a) и (b) найти формулу со следующей таблицей истинности.

$	$	$	???
T	T	T	T
F	T	T	F
T	F	T	F
F	F	T	F
T	T	F	T
F	T	F	T
T	F	F	F
F	F	F	F

г) Используйте метод, предложенный частями (a) — (c), чтобы объясните, почему любой список из $ 2 ^ n $ T и F является последний столбец таблицы истинности для некоторой формулы с $ n $ буквами.

Пример 1.1.5 Если $ P_1, P_2, \ ldots, P_n $ — список формул $ n $, максимальное количество составных формул, использующих этот список, нет двух из которых эквивалентны?

Полный список логических символов

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

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

Предпочитаете версию в формате PDF?

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

Константы

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

Переменные

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

Название символа	Пояснение	Пример
$ x, y, w, z $	Переменные количественного определения	$ x_1 + x_2 = y $
$ \ mathbf {x}, \ mathbf {y}, \ mathbf {w}, \ mathbf {z} $	Метапеременные для переменных количественного определения	Для всех переменных $ \ mathbf {x} _1 $ и $ \ mathbf {x} _2 $, ‘$ \ mathbf {x} _1 = \ mathbf {x} _2 $’ — формула.
$ f, g, h $	Функциональные символы	$ h \ left (f_1 (x), g (x, y) \ right) $
$ \ mathbf {s}, \ mathbf {t} $	Метапеременные для терминов	Для всех терминов $ \ mathbf {t} _1 $ и $ \ mathbf {t} _2 $, ‘$ f (\ mathbf {t} _1, \ mathbf { t} _2) $ ‘- это термин.
$ P, Q, R $	Пропозициональные / Предикатные символы	$ P (x, a) \ land Q_1 (z) $
$ \ alpha, \ beta, \ gamma , \ phi, \ psi $	Метапеременные для формул	Для всех формул $ \ alpha $ и $ \ beta $, $ \ alpha \ land \ beta \ Equiv \ beta \ land \ alpha $.
$ \ Sigma, \ Phi, \ Psi $	Метапеременные для набора предложений	Если $ \ Sigma $ несовместима, то $ \ Sigma \ cup \ Phi $ тоже.
$ \ mathcal {L} $	Метапеременная для формальных языков	Если $ \ mathcal {L} $ — язык с равенством и константой $ a $, то ‘$ a = a $’ будет формула в $ \ mathcal {L} $.

Операторы

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

Унарные логические связки

Имя символа	Пояснение	Пример
$ \ lnot P $, $ \ sim \! \! P $, $ \ overline {P} $	Отрицание $ P $ (не $ P $)	$ \ lnot \ lnot P \ Equiv P $
$ \ Diamond P $	Возможно $ P $	Если $ \ Diamond P $ , то $ \ Diamond \ Diamond P $.
$ \ Box P $	Обязательно $ P $	Если $ \ Box P $, то $ \ neg \ Diamond \ neg P $.

Двоичные логические связки

$ P \ land P \ эквив P $

Название символа	Пояснение	Пример
$ P \ land Q $	Соединение ($ P $ и $ Q $)
$ P \ lor Q $	дизъюнкция ($ P $ или $ Q $)	$ \ neg (P \ lor Q) \ эквив $ $ \ neg P \ land \ neg Q $
$ P \ veebar Q $, $ P \ oplus Q $	Исключительная дизъюнкция ($ P $ xor $ Q $)	$ P \ oplus Q \ Equiv $ $ (P \ lor Q) \ land \ neg (P \ land Q) $
$ P \ uparrow Q $	Отрицание конъюнкции ($ P $ nand $ Q $)	$ P \ uparrow Q \ Equiv \ neg (P \ land Q) $
$ P \ downarrow Q $	Отрицание дизъюнкции ($ P $ или $ Q $)	$ P \ downarrow Q \ Equiv \\ (\ neg P \ land \ neg Q ) $
$ P \ to Q $	Условное (Если $ P $, то $ Q $)	Для всех $ P $, $ P \ to P $ является тавтологией.
$ P \ not \ to Q $	Безусловный (Not ‘if $ P $, then $ Q $’)	$ P \ not \ to Q \ Equiv P \ land \ neg Q $
$ P \ leftarrow Q $	Условное преобразование (Если $ Q $, то $ P $)	$ Q \ leftarrow (P \ land Q) $
$ P \ not \ leftarrow Q $	Converse безусловный (Not ‘if $ Q $, then $ P $’)	$ (P \ to Q) \ land \\ (P \ not \ leftarrow Q) $
$ P \ leftrightarrow Q $	Biconditional ($ P $ тогда и только тогда, когда $ Q $)	$ P \ leftrightarrow Q \ Equiv $ $ (P \ to Q) \ land (P \ leftarrow Q) $
$ P \ not \ leftrightarrow Q $	Non-biconditional (Not ‘$ P $ if and only if $ Q $’)	If $ P \ not \ to Q $, то $ P \ not \ leftrightarrow Q $.2) $
$ \ существует! \ mathbf {x} $	Количественная оценка уникальности (Существует уникальный $ \ mathbf {x} $)	$ \ exists! \, q, r \ in \ mathbb {Z} \, $ $ ( n = dq + r \, \ land $ $ 0 \ le | r |
$ \ mathrm {N} \ mathbf {x} $, $ \ nexists \ mathbf {x} $	Количественная оценка отсутствия ($ \ mathbf {x} $)	$ \ mathrm {N} x P (x) \ Equiv \\ \ forall x \, \ neg P (x) $
$ \ exists_n \ mathbf {x} $	Числовое определение (Есть ровно $ n $ $ \ mathbf {x} $)	$ \ exists_3 x \ in \ mathbb {Z} \, (5 < x <9) $
$ \ exists _ {\ ge n} \ mathbf {x} $	Числовое определение (Есть не менее $ n $ $ \ mathbf {x} $)	$ \ существует _ {\ ge 2} x \, Q (x) \ эквив $ $ \ существует x \ существует y \, (Q (x) \ land $ $ Q (y) \ land x \ ne y) $
$ \ exists _ {\ le n} \ mathbf {x} $	Численное определение 9 1363 (Максимум $ n $ $ \ mathbf {x} $)	$ \ exists _ {\ le 10} x \, (x ^ 2 \ le 100) \ Equiv $ $ \ neg \ left (\ существует _ {\ ge 11} x \, (x ^ 2 \ le 100) \ right) $

Операторы на основе подстановки

Имя символа	Пояснение	Пример
$ \ mathbf {t} [\ mathbf {x} / \ mathbf {t} _0] $	Замещенный термин (термин $ \ mathbf {t} $ с вхождениями $ \ mathbf {x} $ заменен на $ \ mathbf {t} _0 $)	$ (x ^ 2 + y) [x / 1] [y / 5] = $ 1 ^ 2 + 5 $
$ \ mathbf {\ alpha} [\ mathbf {x} / \ mathbf {t_0}] $	Замещенная формула (формула $ \ mathbf {\ alpha} $ с свободными вхождениями $ \ mathbf {x} $ заменена термином $ \ mathbf {t_0} $)	$ (\ forall x (x = y)) [x / a] = $ $ \ forall x (x = y) $

Операторы на основе оценки

Название символа	Пояснение ation	Пример
$ \ mathbf {t} ^ {\ sigma} $	Референт термина $ \ mathbf {t} $ при оценке $ \ sigma $	$ \ left (f ( a, b) \ right) ^ {\ sigma} = $ $ \ mathrm {отец} (\ mathrm {Al}, \ mathrm {Bob}) $
$ \ alpha ^ {\ sigma} $	Истинное значение формулы $ \ alpha $ при оценке $ \ sigma $	Если $ P ^ {\ sigma} $ — симметричное отношение, то $ \ left (P (x, y) \ right) ^ {\ sigma } = \\ \ left (P (y, x) \ right) ^ {\ sigma} $
$ \ sigma (\ mathbf {x} / u) $	Переоценка $ \ sigma $, где переменная $ \ mathbf {x} $ переоценивается как $ u $	$ (\ forall x \, \ alpha) ^ {\ sigma} = \ top $ тогда и только тогда, когда для всех $ u $ во вселенной дискурса $ U $, $ \ alpha ^ {\ sigma (x / u)} = \ top $.

Реляционные символы

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

Имя символа	Пояснение	Пример
$ \ mathbf {t} _1 = \ mathbf {t} _2 $	Идентификационный символ в логической системе с равенством	‘$ \ neg \ left (1 = s (1) \ right) $ ‘- формула на языке арифметики первого порядка.
$ \ alpha \! \ подразумевает \! \ beta $	Предложение $ \ alpha $ подразумевает предложение $ \ beta $	$ \ forall x \, (x \ ge 1) \! \ подразумевает 1 \ ge 1 $
$ \ alpha \! \ impliedby \! \ beta $	Предложение $ \ alpha $ — , подразумеваемое предложением $ \ beta $	$ 5 \ mid x \! \ impliedby \! 5 \ mid 7x $
$ \ alpha \ Equiv \ beta $, $ \ alpha \ Leftrightarrow \ beta $, $ \ alpha \! \ iff \! \ beta $	Предложения $ \ alpha $ и $ \ beta $ логически эквивалентны	$ \ neg (P \ to Q) \ Equiv \\ P \ land \ neg Q $
$ \ sigma \ models \ alpha $	Оценка $ \ sigma $ удовлетворяет формуле $ \ alpha $	Если $ \ phi ^ {\ sigma} = \ top $, то $ \ sigma \ models \ phi $.
$ \ Phi \ models \ phi $	Набор предложений $ \ Phi $ влечет за собой предложения $ \ phi $ ($ \ phi $ является логическим следствием $ \ Phi $)	Если $ \ Phi \ models \ phi $, затем $ \ Phi \ cup \ Psi \ models \ phi $.
$ \ Phi \ nvDash \ phi $	Набор предложений $ \ Phi $ не влечет за собой предложения $ \ phi $	$ \ {P \ to Q, Q \ to R \} \ nvDash R $
$ \ models \ phi $	Предложение $ \ phi $ — тавтология	$ \ models \ forall x \, (x = x) $
$ \ Phi \ vdash \ phi $	Набор предложений $ \ Phi $ доказывает предложение $ \ phi $	$ \ forall x \, P (x, a) \ vdash \\ P (a, a) $
$ \ Phi \ nvdash \ phi $	Набор предложений $ \ Phi $ не доказывает предложение $ \ phi $	$ \ exists x \, R (x) \ nvdash R (a) $
$ \ vdash \ phi $	Предложение $ \ phi $ является теоремой	$ \ vdash \ forall x \ forall y \, (x = y \ to $ $ y = x) $
$ \ phi \ потому что \ Phi $	$ \ phi $, потому что $ \ Phi $	$ A = 95 ^ {\ circ} \ потому что $ $ A + B = 180 ^ {\ circ}, $ $ B = 85 ^ {\ circ} $
$ \ Phi \ следовательно \ phi $	$ \ Phi $, следовательно $ \ phi $	$ P \ lor Q, \ neg P \\ \ поэтому Q $

Для основного списка символов см. математические символы.Списки символов по категориям типа и по теме см. На соответствующих страницах ниже.

Предпочитаете версию в формате PDF?

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

Дополнительные ресурсы

Логические элементы

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

Обозначение

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

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

• ~ A : обратное ( НЕ ) A , когда A соответствует истинному , ~ A ложному
• A + B : значение A OR B
• A · B : значение A AND B
• A ⊕ B : значение исключающего ИЛИ ( XOR ) для A с B
• Q : значение эквивалентного результата (OUTPUT) логического выражения

Результирующее значение Q из логического выражения в отображается как:

Q = A + B

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

~ (A + B) = ~ A · ~ B

Логические операторы

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

Identity

Identity означает, что значение результата совпадает с самим условием.

Q = A

  пусть A = false
пусть Q = A  

Пример — мигание пикселей при нажатии

  let A = false
навсегда (функция () {
    A = ввод.buttonA.isPressed ()
    если) {
        light.setAll (0xff0000)
    } еще {
        light.clear ()
    }
    пауза (500)
})  

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

НЕ (отрицание)

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

Q = ~ A

  пусть A = false
пусть Q =! (A)  

Пример — Мигающие пиксели на не нажатых

  let A = false
навсегда (функция () {
    A = ввод.buttonA.isPressed ()
    если)) {
        light.setAll (0xff0000)
    } еще {
        light.clear ()
    }
    пауза (500)
})  

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

OR (дизъюнкция)

Оператор OR приводит к истинно , когда одно или несколько условий истинно .

Q = A + B

  пусть A = false
пусть B = false
пусть Q = A || В  

Пример — Мигает при любом нажатии

  let A = false
пусть B = false
навсегда (функция () {
    A = ввод.buttonA.isPressed ()
    B = input.buttonB.isPressed ()
    if (A || B) {
        light.setAll (0xff0000)
    } еще {
        light.clear ()
    }
    пауза (500)
})  

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

A	B	А + В
Ф	F	F
т	F	т
Ф	т	т
т	т	т

AND (соединение)

Оператор AND требует, чтобы все условия были истинно , чтобы результат был истинно .

Q = A · B

  пусть A = false
пусть B = false
пусть Q = A && B  

Пример — мигание только при двойном нажатии

  let A = false
пусть B = false
навсегда (функция () {
    A = input.buttonA.isPressed ()
    B = input.buttonB.isPressed ()
    if (A && B) {
        light.setAll (0xff0000)
    } еще {
        light.clear ()
    }
    пауза (500)
})  

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

A	B	A · B
Ф	F	F
т	F	F
Ф	т	F
т	т	т

XOR (Исключающее ИЛИ)

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

Q = A ⊕ B

  пусть A = false
пусть B = false
пусть Q = (A || B) &&! (A && B)  

Пример — Мигает при одном нажатии или другом

  let A = false
пусть B = false
навсегда (функция () {
    A = input.buttonA.isPressed ()
    B = ввод.buttonB.isPressed ()
    if ((A || B) &&! (A && B)) {
        light.setAll (0xff0000)
    } еще {
        light.clear ()
    }
    пауза (500)
})  

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

A	B	A ⊕ B
Ф	F	F
т	F	т
Ф	т	т
т	т	F

Математическое форматирование как текст: набор и логическая нотация

.

Набор текста форматирование	Только текст форматирование	Банкноты
(2, 3)	(2, 3)	В скобках укажите баллы.Квадратные скобки и другие обозначения (или вообще ничего) имеют другое значение.
(2, 3)	(2, 3)	Когда вы пишете открытый интервал, используйте круглые скобки и обратите внимание, что «это интервал», чтобы отличать интервал от точки.
[2, 3]	[2, 3]	Используйте квадратные скобки для обозначения закрытых интервалов.
[2, ∞)	[2, бесконечность) [2, бесконечность)	Для «бесконечности» либо произнесите слово по буквам, либо сократите до «inf.». Не пытайтесь аппроксимировать символ бесконечности двумя строчными буквами О. Кстати, никогда не используйте квадратную скобку на бесконечности. «Бесконечность» — это не число, поэтому вы не можете «включить» его в интервал.
A ∪ B	A-соединение-B A U B	Если вы не разобрали объединение множеств (как в первой строке слева), то определите вашу нотацию.B	Если вы не указали пересечение множества, определите ваши обозначения, чтобы читатель не ошибся, что карат указывает на показатель степени.
А ⊂ В	A-подмножество-B A	Если вы не разъясняете отношение подмножества, определите, что вы подразумеваете под символом «меньше».
A ⊆ B	A-подмножество или аналогичное-B A <= B	Если вы не указываете отношение подмножества, определите вашу нотацию «меньше или равно».c	Либо сформулируйте отношение дополнения, либо определите «в степени c» как «набор дополнений».
А — В	A-дополнение-B A — B	Вы можете описать отношение дополнения, если хотите, но почти все понимают обозначение «минус».
a ∈ A	a находится в A a-элемент -A	Символ «является элементом» — непростой.Не пытайтесь приблизить его с помощью заглавной буквы E; даже несмотря на то, что «все» пытаются его использовать, читателей это почти всегда сбивает с толку. (Можно подумать, что мы научимся, но … нет.) Просто объясните отношения.
a ∉ A	a не входит в A a не является элементом A	Укажите отношение.
∅	{} пустой набор Ø	Фигурные скобки обычно используются для обозначения наборов, поэтому вы можете использовать фигурные скобки без каких-либо элементов между ними для обозначения пустого набора.Или (на ПК), удерживая нажатой клавишу «ALT», введите «0216» на цифровой клавиатуре.
{1, 2, 3}	{1, 2, 3}	Наборы обычно записываются с помощью фигурных скобок. Не используйте круглые скобки или другие символы группировки или, что еще хуже, вообще не используйте символы группировки.
	N {1, 2, 3 ,…} натуральные числа	Если вы используете только букву «N» для обозначения «набора натуральных чисел», скажите читателю, что вы имеете в виду.
	Z {…, -1, 0, 1, 2, …} целые числа	Если вы используете только букву «Z» для обозначения «набора целых чисел», скажите читателю, что вы имеете в виду. В противном случае укажите набор, который вы имеете в виду.
	R Реальные числа	Если вы используете только букву «R» для «набора всех действительных чисел», определите обозначение. В противном случае укажите набор, который вы имеете в виду.
	Q рациональные значения	Если вы используете только букву «Q» для «набора всех рациональных чисел» (то есть набора всех дробей), определите обозначение.В противном случае укажите набор, который вы имеете в виду.
	C комплексные числа	Если вы используете «C» для «набора всех комплексных чисел», определите нотацию. В противном случае укажите набор, который вы имеете в виду.
⇒	если (это), то (то) ==>	Либо укажите отношение «если-то», либо приблизьте стрелку, используя два знака «равно», чтобы отличить «если-то» от «больше или равно».
⇔	iff тогда и только тогда, когда <==>	Сокращение «iff» для «тогда и только тогда» является довольно стандартным и должно быть распознано в контексте, но разъясняет вещи, если вы не уверены.
∃	существует (а)	Не пытайтесь подделать этот символ. и	В контексте логического утверждения, карат следует распознать как значение «и», но поясните, если вы не уверены.
∨	v или	Использование «v» вместо символа «или» может сбивать с толку, поэтому либо объясните, что вы имеете в виду, либо четко определите, что вы имеете в виду под «v».
˜ ¬	~ ! не	Существуют различные символы для «не», поэтому определите свое обозначение, независимо от того, что вы используете.На практике часто проще всего использовать «не — (что угодно)».

Учебное пособие по таблице истинности логической алгебры — объяснение XOR, NOR и логических символов

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

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

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

Что такое булева алгебра?

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

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

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

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

Эти символы не имеют самостоятельного значения. Они представляют собой какое-то другое количество. Именно эта величина придает значение этим символам, и именно с этой величиной фактически выполняются операции.

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

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

На изображении ниже показан весь набор вещественных чисел. Набор действительных чисел включает натуральные числа (1, 2, 3, 4 ….), целые числа (все натуральные числа и 0), целые числа (…..- 2, -1, 0, 1, 2, 3 …) и так далее. Обычная алгебра имеет дело со всем этим набором чисел.

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

Например, в информатике мы чаще всего представляем эти значения с помощью 0 и 1.0 используется для False и 1 для True.

Вы также можете сделать это более изящными способами, представив значения истинности некоторыми другими символами, такими как Кошки и Собаки или Бананы и Апельсины.

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

Теперь вопрос в том, что если (Истина и Ложь), (0 и 1) — это просто представления, то что они пытаются представить?

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

Предложение — это просто утверждение вроде «Все кошки милые».

Если вышеприведенное утверждение верно, то мы присваиваем ему значение истинности «Истина» или «1», в противном случае мы присваиваем ему «Ложь» или «0».

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

Логические операции и таблицы истинности

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

В логической алгебре есть три основных операции.

ИЛИ : Также известен как Дизъюнкция . Эта операция выполняется с двумя логическими переменными.Результат операции ИЛИ будет 0, когда оба операнда равны 0, в противном случае будет 1.

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

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

ИЛИ Операция

Переменная-1 Переменная-2 Выход
  0 0 0
  0 1 1
  1 0 1
  1 1 1  

И : Также известна как Соединение .Эта операция выполняется с двумя логическими переменными. Результатом операции И будет 1, когда оба операнда равны 1, в противном случае — 0. Таблица истинности представлена ​​следующим образом.

  И Эксплуатация

Переменная-1 Переменная-2 Выход
  0 0 0
  0 1 0
  1 0 0
  1 1 1  

НЕ : Также известно как Отрицание . Эта операция выполняется только с одной переменной. Если значение переменной равно 1, то эта операция просто преобразует его в 0, а если значение переменной равно 0, то оно преобразует его в 1.

  Не работает

Выход переменной-1
  0 1
  1 0  

Булева алгебра и цифровые схемы

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

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

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

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

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

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

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

  NAND Gate

Переменная-1 Переменная-2 Выход
  0 0 1
  0 1 1
  1 0 1
  1 1 0  

NOR : ворота NOR образованы комбинацией элементов NOT и OR.Элемент ИЛИ-НЕ дает на выходе 1, если оба входа равны 0, в противном случае — 0.

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

  NOR Gate

Переменная-1 Переменная-2 Выход
  0 0 1
  0 1 0
  1 0 0
  1 1 0  

Большинство цифровых схем построено с использованием логических элементов И-НЕ или ИЛИ-ИЛИ из-за их функциональной полноты, а также из-за того, что их легко изготовить.

Помимо вышеупомянутых ворот, у нас также есть некоторые особые ворота, которые служат определенной цели. Это следующие элементы:

XOR : вентиль XOR или вентиль Исключающее ИЛИ — это особый тип логического элемента, который дает 0 на выходе, если оба входа равны 0 или 1, в противном случае он дает 1.

  XOR Ворота

Переменная-1 Переменная-2 Выход
  0 0 0
  0 1 1
  1 0 1
  1 1 0  

XNOR : вентиль XNOR или вентиль Exclusive-NOR — это особый тип логического элемента, который дает 1 на выходе, когда оба входа равны 0 или 1, в противном случае он дает 0.

  XNOR Ворота

Переменная-1 Переменная-2 Выход
  0 0 1
  0 1 0
  1 0 0
  1 1 1  

Заключение

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

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

Логика и выражения

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

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

Истинные утверждения

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

• Наружная температура очень низкая И У меня нет пальто = Мне холодно
• НЕ больной = Я чувствую себя хорошо
• Я умею плавать ИЛИ Я в лодке = Я плыву

Вы видите И, НЕ и ИЛИ в примере словесных уравнений? Это наши логические операторов .Каждый день мы принимаем решения, когда вместе думаем об одном или нескольких фактах, используя эти операторы. Иногда для того, чтобы заключение было правдой, необходимо, чтобы все факты были правдой. Это тот случай, когда используется оператор AND. При анализе фактов с помощью оператора ИЛИ, только факт должен быть верным, чтобы заключение также было верным.

Для принятия решения может потребоваться более одного или двух фактов. Когда это происходит, нужен другой оператор, чтобы объединить факты и сделать вывод.В последнем примере слова «уравнение» вы на самом деле можете не плавать, если выполняются только эти два условия. Чтобы правильно доказать, что вы действительно плаваете, вам нужно указать, что вы тоже в воде.

• ( Я умею плавать ИЛИ Я в лодке ) И Я в воде = Я плыву

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

Булева алгебра

Чтобы привести условия или факты, как мы их называли, к более компактной форме, была изобретена алгебра. Джордж Буль создал арифметику (булеву алгебру), которая использует символы для обозначения условий, операторов и результата. Условия считаются переменными, имеющими значение истинно или ложно .такие операторы, как AND, OR и NOT, являются односимвольными символами. Если мы хотим изменить утверждение «Я счастлив, когда солнечно или когда я ем пончик» в логическое уравнение, мы могли бы начать с преобразования условий в переменные.

• Переменная A = «Солнечно»
• Переменная B = «Я съел пончик»

В результате получается переменная с именем Q , которая истинна, когда вы счастливы, и представляет собой значение операции A с B .Это операция ИЛИ, которая представлена ​​символом + .

Q = A + B

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

• Переменная C = «Я в отпуске»

Q = A + B + C

Может быть, вам легко угодить, и вам просто нужно хорошо себя чувствовать, чтобы быть счастливым.Итак, вы счастливы, когда НЕ болеете. Мы будем использовать ~ для обозначения НЕ в нашем уравнении.

Q = ~ A

В ситуации, когда все условия должны быть истинными, чтобы результат был истинным, условия используют операцию AND. Чтобы солнце светило на вас, небо должно быть чистым и днем. Мы соединяем эти два факта с символом И · .

• Переменная A = «Небо чистое»
• Переменная B = «Сейчас день»
• Результат Q = «Солнце светит»

Q = A · B

Выражения

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

• Переменная A = «Небо чистое»
• Переменная B = «Сейчас день»
• Результат Q = «Солнце светит»
• Результат ~ Q = «Солнце НЕ светит»

Чтобы сделать «солнце светит» противоположностью , мы инвертируем, используем символ НЕ в обеих частях уравнения.

~ Q = ~ (A · B)

А теперь давайте представим, что солнце НЕ светит из-за неблагоприятных условий. Если небо не ясное ИЛИ не дневное время, значит, солнце не светит. Таким образом, символ НЕ ставится перед переменными для каждого условия, так что «солнце НЕ светит» имеет другое уравнение, подобное этому:

~ Q = ~ A + ~ B

Мы видим, что сторона с переменными A и B в обоих уравнениях эквивалентна друг другу, поскольку обе они равны ~ Q :

~ (A · B) = ~ A + ~ B

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

Таможня Де Моргана

Последнее уравнение, ~ (A · B) = ~ A + ~ B , демонстрирует важное свойство в булевой алгебре. Он называется «Тамом» Де Моргана, в котором говорится, что обратное (НЕ) конъюнкции (И) логически эквивалентно дизъюнкции (ИЛИ) двух обратных (НЕ). Кроме того, обратное (НЕ) дизъюнкции (ИЛИ) логически эквивалентно соединению (И) двух обратных (НЕ).

Это легче понять, увидев булевы уравнения для обоих случаев:

~ (A · B) = ~ A + ~ B

— И —

~ (A + B) = ~ A · ~ B

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

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

Холодно	У меня нет пальто	Мне холодно
ложный	ложь	ложь
ложный	правда	ложь
истина	ложь	ложь
истина	правда	правда

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

• Переменная A = «замерзает»
• Переменная B = «У меня нет пальто»

A · B = Q

Таблица истинности для переменных в выражении имеет те же значения, что и таблица для утверждения истинности ( истина, и ложь, сокращены до T и F ).

А	B	Q
Ф	F	F
Ф	т	F
т	F	F
т	F	т

Что произойдет, если мы изменим условие «У меня нет пальто» на «У меня есть пальто» ? Как это влияет на таблицу истинности того, насколько холодно вы себя чувствуете?

Холодно	у меня пальто	Мне холодно
ложный	ложь	ложь
ложный	правда	ложь
истина	ложь	правда
истина	правда	ложь

А	B	Q
Ф	F	F
Ф	т	F
т	F	т
т	F	F

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