Знаки алгебра логики: Алгебра логики — Википедия – § 1.3. Элементы алгебры логики — RC74 — интернет-магазин радиоуправляемых моделей

Содержание

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

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

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

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

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

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

Пример. «3 – простое число» является высказыванием, поскольку оно истинно.

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

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

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

Пример. «x+2>5» — высказывательная форма, которая при x>3 является истинной, иначе ложной.

Алгебра логики рассматривает любое высказывание только с одной точки зрения – является ли оно истинным или ложным. Слова и словосочетания «не», «и», «или», «если…, то», «тогда и только тогда» и другие позволяют из уже заданных высказываний строить новые высказывания. Такие слова и словосочетания называются логическими связками.

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

(сложными). Высказывания, которые не являются составными, называются элементарными (простыми).

Пример. высказывание «Число 6 делится на 2» — простое высказывание. Высказывание «Число 6 делится на 2, и число 6 делится на 3» — составное высказывание, образованное из двух простых с помощью логической связки «и».

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

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

Пример. Обозначим через А простое высказывание «число 6 делится на 2», а через В простое высказывание «число 6 делится на 3». Тогда составное высказывание «Число 6 делится на 2, и число 6 делится на 3» можно записать как «А и В». Здесь «и» – логическая связка, А, В – логические переменные, которые могут принимать только два значения – «истина» или «ложь», обозначаемые, соответственно, «1» и «0».

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

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

Обозначение операции	Читается	Название операции	Альтернативные обозначения
⌐	НЕ	Отрицание (инверсия)	Черта сверху
˄	И	Конъюнкция (логическое умножение)	∙ &
ν	ИЛИ	Дизъюнкция (логическое сложение)	+
→	Если … то	Импликация
↔	Тогда и только тогда	Эквиваленция	~
XOR	Либо …либо	Исключающее ИЛИ (сложение по модулю 2)

НЕ Операция, выражаемая словом «не», называется отрицанием и обозначается чертой над высказыванием (или знаком ). Высказывание А истинно, когда A ложно, и ложно, когда A истинно.

Пример. Пусть А=«Сегодня пасмурно», тогда А=«Сегодня не пасмурно».

И Операция, выражаемая связкой «и», называется

конъюнкцией (лат. conjunctio – соединение) или логическим умножением и обозначается точкой « • » (может также обозначаться знаками или &). Высказывание А • В истинно тогда и только тогда, когда оба высказывания А и В истинны.

Пример. Высказывание «Число 6 делится на 2, и число 6 делится на 3» — истинно, а высказывание «Число 6 делится на 2, и число 6 больше 10» — ложно.

ИЛИ Операция, выражаемая связкой «или» (в неисключающем смысле этого слова), называется дизъюнкцией (лат. disjunctio – разделение) или логическим сложением.

Пример: Высказывание «Число 6 делится на 2 или число 6 больше 10» — истинно, а высказывание «Число 6 делится на 5 или число 6 больше 10» — ложно.

ЕСЛИ … ТО Операция, выражаемая связками «если …, то», «из … следует», «… влечет …», называется импликацией (лат. implico – тесно связаны) и обозначается знаком → . Высказывание А→В ложно тогда и только тогда, когда А истинно, а В ложно.

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

РАВНОСИЛЬНО Операция, выражаемая связками «тогда и только тогда»,

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

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

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

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

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

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

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

Логика очень древняя наука. Ещё в античные времена была известна

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

Высказывания бывают общими, частными и единичными. Общее высказывание начинается со слов: всё, все, всякий, каждый, ни один. Частное высказывание начинается со слов: некоторые, большинство и т.п. Во всех других случаях высказывание является единичным.
Формальная логика была известна в средневековой Европе, она развивалась и обогащалась новыми законами и правилами, но при этом вплоть до 19 века она оставалась обобщением конкретных содержательных данных и её законы сохраняли форму высказываний на разговорном языке.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Список логических символов — List of logic symbols

Условное обозначение	название	объяснение	Примеры	Unicode , значение (шестнадцатеричное)	HTML значение (десятичный)	HTML объект (названный)	LaTeX символ
	Читайте также
	категория
	материальная импликация	A⇒В{\ Displaystyle А \ Rightarrow В}истинно тогда и только тогда , когда может быть правдой , и может быть ложным , но не наоборот. может означать , так же , как (символ может также указывать домен и кообласть в функции , см таблицу математических символов ). может означать , так же , как (символ может также означать надмножество ). В{\ Displaystyle B}A{\ Displaystyle A} →{\ Displaystyle \ СтрелкаВправо}⇒{\ Displaystyle \ Rightarrow} ⊃{\ Displaystyle \ supset}⇒{\ Displaystyle \ Rightarrow}	Иксзнак равно2⇒Икс2знак равно4{\ Displaystyle х = 2 \ Rightarrow х ^ {2} = 4}это верно, но это в общем неверно (так как может быть -2). Икс2знак равно4⇒Иксзнак равно2{\ Displaystyle х ^ {2} = 4 \ Rightarrow х = 2}Икс{\ Displaystyle х}	U + 21D2 U + 2192 U + 2283	& # 8658; & # 8594; & # 8835;	& rArr; & rarr; & вечерять;	⇒{\ Displaystyle \ Rightarrow}\ Rightarrow \ или \ СтрелкаВправо \ supset \ означает →{\ Displaystyle \ к} ⊃{\ Displaystyle \ supset} ⟹{\ Displaystyle \ означает}
	предполагает; если .. то
	пропозициональная логика , гейтингова алгебра
	материал эквивалентности	A⇔В{\ Displaystyle А \ Leftrightarrow В}верно только если оба и являются ложными, или оба и являются истинными. A{\ Displaystyle A}В{\ Displaystyle B}A{\ Displaystyle A}В{\ Displaystyle B}	Икс+5знак равноY+2⇔Икс+3знак равноY{\ Displaystyle х + 5 = у + 2 \ Leftrightarrow х + 3 = у}	U + 21D4 U + 2261 U + 2194	& # 8660; & # 8801; & # 8596;	& Harr; & эквив; & Harr;	⇔{\ Displaystyle \ Leftrightarrow}\ Leftrightarrow \ эквив \ leftrightarrow \ тогда и только тогда ≡{\ Displaystyle \ эквив} ↔{\ Displaystyle \ leftrightarrow} ⟺{\ Displaystyle \ тогда и только тогда}
	если и только если; тогда и только тогда; означает то же,
	логика высказываний
	отрицание	Утверждение истинно , если и только если ложно. Косая черта размещаемых посредством другого оператора такой же , как размещены в передней. ¬A{\ Displaystyle \ lnot A}A{\ Displaystyle A} ¬{\ Displaystyle \ отр}	¬(¬A)⇔A{\ Displaystyle \ отр (\ отр А) \ Leftrightarrow А} Икс≠Y⇔¬(Иксзнак равноY){\ Displaystyle х \ NEQ у \ Leftrightarrow \ отр (х = у)}	U + 00AC U + 02DC U + 0021	& # 172; & # 732; & # 33;	&не; & тильда; & плюс;	¬{\ Displaystyle \ отр}\ lnot или \ отр \ сим ~{\ Displaystyle \ сим}
	не
	логика высказываний
	логическое соединение	Заявление ∧ B является истинным , если и B оба являются истинными; в противном случае оно ложно.	п <4 ∧ п > 2 ⇔ п = 3 , когда п является натуральным числом .	U + 2227 U + 00B7 U + 0026	& # 8743; & # 183; & # 38;	&а также; & Мидот; & амп;	∧{\ Displaystyle \ клин}\ клин или \ земля \ & &{\ Displaystyle \ &}
	а также
	пропозициональная логика , булева алгебра
	логический (включительно) дизъюнкция	Утверждение ∨ B истинно , если или Б (или оба) являются истинными; если оба ложны, то утверждение ложно.	п ≥ 4 ∨ п ≤ 2 ⇔ п ≠ 3 , когда п является натуральным числом .	U + 2228 U + 002B U + 2225	& # 8744; & # 43; & # 8741;	&или же;	∨{\ Displaystyle \ лор}\ лор или \ ви \ параллельно ∥{\ Displaystyle \ параллельно}
	или же
	пропозициональная логика , булева алгебра
	эксклюзивная дизъюнкция	Заявление ⊕ B истинно , когда А или В, но не оба, являются правдой. ⊻ В означает то же самое.	(¬ ) ⊕ всегда верно, и ⊕ всегда ложно, если бессодержательная истина исключается.	U + 2295 U + 22BB	& # 8853; & # 8891;	& Oplus;	⊕{\ Displaystyle \ oplus}\ oplus \ veebar ⊻{\ Displaystyle \ veebar}
	исключающее
	пропозициональная логика , булева алгебра
	тавтология	Заявление ⊤ безусловно верно.	⇒ ⊤ всегда верно.	U + 22A4	& # 8868;		⊤{\ Displaystyle \ сверху}\Топ
	сверху, Верум
	пропозициональная логика , булева алгебра
	Противоречие	Заявление ⊥ безусловно неверно. (Символ ⊥ может также относиться к перпендикулярным линиям.)	⊥ ⇒ всегда верно.	U + 22A5	& # 8869;	& Преступник;	⊥{\ Displaystyle \ бот}\ бот
	дно, константа ‘ложь, ложь
	пропозициональная логика , булева алгебра
	универсальный количественное	∀ х : Р ( х ) или ( х ) Р ( х ) означает , что Р ( х ) верно для всех х .	∀ п ∈ ℕ: п ² ≥ п .	U + 2200	& # 8704;	&для всех;	∀{\ Displaystyle \ FORALL}\для всех
	для всех; для любого; для каждого
	Логика первого порядка
∃	экзистенциальная количественное	∃ х : Р ( х ) означает , что существует по крайней мере один х такой , что Р ( х ) истинно.	∃ п ∈ ℕ: п четно.	U + 2203	& # 8707;	&существовать;	∃{\ Displaystyle \ существует}\существует
	Существует
	Логика первого порядка
∃!	единственность	∃! х : Р ( х ) означает , что существует ровно один х , таких , что Р ( х ) истинно.	∃! п ∈ ℕ: п + 5 = 2 н .	U + 2203 U + 0021	& # 8707; & # 33;		∃!{\ Displaystyle \ существует!}\существует !
	существует ровно один
	Логика первого порядка
	определение	х ≔ у или х ≡ у означает й определяются как другое название у (но обратите внимание , что ≡ может также означать , другие вещи, такие как конгруэнция ). Р : ⇔ Q означает Р определяется как логически эквивалентны с Q .	сп х ≔ (1/2) (ехр х + ехр (- х )) исключающее ИЛИ Б : ⇔ ( ∨ B ) ∧ ¬ ( ∧ B )	U + 2254 (U + 003A U + 003D) U + 2261 U + 003A U + 229C	& # 8788; (& # 58; & # 61;) & # 8801; & # 8860;	& эквив; & Harr;	знак равно{\ Displaystyle: =}: = \ Эквив : \ Leftrightarrow ≡{\ Displaystyle \ эквив} : ⇔{\ Displaystyle: \ Leftrightarrow}
	определяется как
	везде
()	старшинство группировка	Выполните операции внутри скобок сначала.	(8 ÷ 4) ÷ 2 = 2 ÷ 2 = 1, но 8 ÷ (4 ÷ 2) = 8 ÷ 2 = 4.	U + 0028 U + 0029	& # 40; & # 41;		( ){\ Displaystyle (~)} ()
	круглые скобки, скобки
	везде
⊢	турникет	х ⊢ у означает у выводим из й (в некоторой заданной формальной системе).	→ B ⊢ ¬ B → ¬	U + 22A2	& # 8866;		⊢{\ Displaystyle \ vdash}\ vdash
	доказуемый
	логика высказываний , первый порядок логика
⊨	двойной турникет	х ⊨ у средства х семантически влечет у	→ B ⊨ ¬ B → ¬	U + 22A8	& # 8872;		⊨{\ Displaystyle \ vDash}\ vDash, \ модели
	влечет за собой
	логика высказываний , первый порядок логика

Логика высказываний — Википедия

Логика высказываний, пропозициональная логика (лат. propositio — «высказывание»^[1]) или исчисление высказываний^[2] — это раздел символической логики, изучающий сложные высказывания, образованные из простых, и их взаимоотношения. В отличие от логики предикатов, пропозициональная логика не рассматривает внутреннюю структуру простых высказываний, она лишь учитывает, с помощью каких союзов и в каком порядке простые высказывания сочленяются в сложные^[3].

Несмотря на свою важность и широкую сферу применения, логика высказываний является простейшей логикой и имеет очень ограниченные средства для исследования суждений^[2].

Язык логики высказываний (пропозициональный язык^[4]) — формализованный язык, предназначенный для анализа логической структуры сложных высказываний^[1].

Алфавит языка логики высказываний[править | править код]

Исходные символы, или алфавит языка логики высказываний, разделены на следующие три категории^[1]^[5]:

пропозициональные буквы (пропозициональные переменные):

p,q,r,s,t,p1,q1,r1,s1,t1,…{\displaystyle p,q,r,s,t,p_{1},q_{1},r_{1},s_{1},t_{1},…}

логические знаки (логические союзы):

Пропозициональные переменные[править | править код]

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

Пропозициональные формулы[править | править код]

Роль структурных образований, аналогичных элементарным и сложным высказываниям, играют в этом языке формулы. Пропозициональная формула — слово языка логики высказываний^[6], т.е. конечная последовательность знаков алфавита, построенная по изложенным ниже правилам и образующая законченное выражение языка логики высказываний^[1]. Заглавные латинские буквы A{\displaystyle A}, B{\displaystyle B} и другие, которые употребляются в определении формулы, принадлежат не языку логики высказываний, а его метаязыку, то есть языку, который используется для описания самого языка логики высказываний. Содержащие метабуквы выражения ¬A{\displaystyle \neg A}, (A→B){\displaystyle (A\to B)} и другие — не пропозициональные формулы, а схемы формул. Например, выражение (A∧B){\displaystyle (A\wedge B)} есть схема, под которую подходят формулы (p∧q){\displaystyle (p\wedge q)}, (p∧(r∨s)){\displaystyle (p\wedge (r\vee s))} и другие^[1].

Индуктивное определение формулы логики высказываний:^[4]^[1]

пропозициональная переменная есть формула;
если A{\displaystyle A} — произвольная формула, то ¬A{\displaystyle \neg A} — тоже формула;
если A{\displaystyle A} и B{\displaystyle B} — произвольные формулы, то (A→B){\displaystyle (A\to B)}, (A∧B){\displaystyle (A\wedge B)}, (A↔B){\displaystyle (A\leftrightarrow B)}, (A∨B){\displaystyle (A\vee B)} и (A ∨˙ B ){\displaystyle (A~{\dot {\lor }}~B~)} — тоже формулы.

Других формул в языке логики высказываний нет.

Относительно любой последовательности знаков алфавита языка логики высказываний можно решить, является она формулой или нет. Если эта последовательность может быть построена в соответствии с пп. 1—3 определения формулы, то она формула, если нет, то не формула^[1].

Соглашения о скобках[править | править код]

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

Если опущены внешние скобки, то они восстанавливаются.
Если рядом стоят две конъюнкции или дизъюнкции (например, A∧B∧C{\displaystyle A\wedge B\wedge C}), то в скобки заключается сначала самая левая часть (то есть две подформулы со связкой между ними). (Говорят также, что эти связки левоассоциативны.)
Если рядом стоят разные связки, то скобки расставляются согласно приоритетам: ¬,∧,∨{\displaystyle \neg ,\wedge ,\vee } и →{\displaystyle \to } (от высшего к низшему).

Когда говорят о длине формулы, имеют в виду длину подразумеваемой (восстанавливаемой) формулы, а не сокращённой записи.

Например: запись A∨B∧¬C{\displaystyle A\vee B\wedge \neg C} означает формулу (A∨(B∧(¬C))){\displaystyle (A\vee (B\wedge (\neg C)))}, а её длина равна 12.

Формализация и интерпретация[править | править код]

Как и любой другой формализованный язык, язык логики высказываний можно рассматривать как множество всех слов, построенных с использованием алфавита этого языка^[7]. Язык логики высказываний можно рассматривать как множество всевозможных пропозициональных формул^[4]. Предложения естественного языка могут быть переведены на символический язык логики высказываний, где они будут представлять из себя формулы логики высказываний. Процесс перевода высказывания в формулу языка логики высказываний называется формализацией. Обратный процесс подстановки вместо пропозициональных переменных конкретных высказываний называется интерпретацией^[8].

Аксиомы и правила вывода формальной системы логики высказываний[править | править код]

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

A1:A→(B→A){\displaystyle A_{1}:A\rightarrow (B\rightarrow A)};

A2:(A→(B→C))→((A→B)→(A→C)){\displaystyle A_{2}:(A\rightarrow (B\rightarrow C))\rightarrow ((A\rightarrow B)\rightarrow (A\rightarrow C))};

A3:A∧B→A{\displaystyle A_{3}:A\wedge B\rightarrow A};

A4:A∧B→B{\displaystyle A_{4}:A\wedge B\rightarrow B};

A5:A→(B→(A∧B)){\displaystyle A_{5}:A\rightarrow (B\rightarrow (A\wedge B))};

A6:A→(A∨B){\displaystyle A_{6}:A\rightarrow (A\vee B)};

A7:B→(A∨B){\displaystyle A_{7}:B\rightarrow (A\vee B)};

A8:(A→C)→((B→C)→((A∨B)→C)){\displaystyle A_{8}:(A\rightarrow C)\rightarrow ((B\rightarrow C)\rightarrow ((A\vee B)\rightarrow C))};

A9:¬A→(A→B){\displaystyle A_{9}:\neg A\rightarrow (A\rightarrow B)};

A10:(A→B)→((A→¬B)→¬A){\displaystyle A_{10}:(A\rightarrow B)\rightarrow ((A\rightarrow \neg B)\rightarrow \neg A)};

A11:A∨¬A{\displaystyle A_{11}:A\vee \neg A}.

вместе с единственным правилом:

A(A→B)B{\displaystyle {\frac {A\quad (A\rightarrow B)}{B}}} (Modus ponens)

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

Таблицы истинности основных операций[править | править код]

Основной задачей логики высказываний является установление истинностного значения формулы, если даны истинностные значения входящих в неё переменных. Истинностное значение формулы в таком случае определяется индуктивно (с шагами, которые использовались при построении формулы) с использованием таблиц истинности связок^[9].

Пусть B{\displaystyle \mathbb {B} } — множество всех истинностных значений {0,1}{\displaystyle \{0,1\}}, а Vars{\displaystyle Vars} — множество пропозициональных переменных. Тогда интерпретацию (или модель) языка логики высказываний можно представить в виде отображения

M:Vars→B{\displaystyle M\colon Vars\to \mathbb {B} },

которое каждую пропозициональную переменную p{\displaystyle p} сопоставляет с истинностным значением M(p){\displaystyle M(p)}^[9].

Оценка отрицания ¬p{\displaystyle \neg p} задаётся таблицей:

Значения двухместных логических связок →{\displaystyle \rightarrow } (импликация), ∨{\displaystyle \vee } (дизъюнкция) и ∧{\displaystyle \wedge } (конъюнкция) определяются так:

Тождественно истинные формулы (тавтологии)[править | править код]

Формула является тождественно истинной, если она истинна при любых значениях входящих в неё переменных (то есть, при любой интерпретации)^[10]. Далее перечислены несколько широко известных примеров тождественно истинных формул логики высказываний:

¬(p∨q)↔(¬p∧¬q){\displaystyle \neg (p\vee q)\leftrightarrow (\neg p\wedge \neg q)};

¬(p∧q)↔(¬p∨¬q){\displaystyle \neg (p\wedge q)\leftrightarrow (\neg p\vee \neg q)};

(p→q)↔(¬q→¬p){\displaystyle (p\rightarrow q)\leftrightarrow (\neg q\rightarrow \neg p)};

законы поглощения:

p∨(p∧q)↔p{\displaystyle p\vee (p\wedge q)\leftrightarrow p};

p∧(p∨q)↔p{\displaystyle p\wedge (p\vee q)\leftrightarrow p};

p∧(q∨r)↔(p∧q)∨(p∧r){\displaystyle p\wedge (q\vee r)\leftrightarrow (p\wedge q)\vee (p\wedge r)};

p∨(q∧r)↔(p∨q)∧(p∨r){\displaystyle p\vee (q\wedge r)\leftrightarrow (p\vee q)\wedge (p\vee r)}.

↑ ¹ ² ³ ⁴ ⁵ ⁶ ⁷ Чупахин, Бродский, 1977, с. 203—205.
↑ ¹ ² Кондаков, 1971, статья «Исчисление высказываний».
↑ ¹ ² НФЭ, 2010.
↑ ¹ ² ³ Герасимов, 2011, с. 13.
↑ Войшвилло, Дегтярев, 2001, с. 91—94.
↑ Эдельман, 1975, с. 130.
↑ Эдельман, 1975, с. 128.
↑ Игошин, 2008, с. 32.
↑ ¹ ² Герасимов, 2011, с. 17—19.
↑ Герасимов, 2011, с. 19.

Кондаков Н. И. Логический словарь / Горский Д. П.. — М.: Наука, 1971. — 656 с.
Эдельман С. Л. Математическая логика. — М.: Высшая школа, 1975. — 176 с.
Чупахин И. Я.,Бродский И. Н. Формальная логика. — Ленинград: Издательство Ленинградского университета, 1977. — 357 с.
Войшвилло Е. К., Дегтярев М. Г. Логика. — М.: ВЛАДОС-ПРЕСС, 2001. — 528 с. — ISBN 5-305-00001-7.
Игошин В. И. Математическая логика и теория алгоритмов. — 2-е изд., стереотип.. — М.: Издательский центр «Академия», 2008. — 448 с. — ISBN 978-5-7695-4593-1.
Логика высказываний // Новая философская энциклопедия. — М., 2010. — Т. 2. — С. 415—418.
Герасимов А. С. Курс математической логики и теории вычислимости. — СПб.: Издательство «ЛЕМА», 2011. — 284 с. — ISBN 978-5-98709-292-7.

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

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

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

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

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

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

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

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

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

Пример.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пусть высказывание А истинно. Вы живете в Самаре. Если А истина, то НЕ А ложно. Если А ложно, то НЕ А истина.

2. Следующая логическая операция конъюнкция — логическое умножение.

Обозначается следующим образом: ^, •, &, И, and

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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