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

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

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

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

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

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

Пример. «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 \ бот}\ бот
	дно, константа ‘ложь, ложь
	пропозициональная логика , булева алгебра
	универсальный количественное	∀  х :  Р ( х ) или ( х )  Р ( х ) означает , что Р ( х ) верно для всех х .	∀  п  ∈ ℕ: п 2  ≥ п .	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]

1. пропозициональная переменная есть формула;
2. если A{\displaystyle A} — произвольная формула, то ¬A{\displaystyle \neg A} — тоже формула;
3. если 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)}.

1. ↑ ^{1 2 3 4 5 6 7} Чупахин, Бродский, 1977, с. 203—205.
2. ↑ ^{1 2} Кондаков, 1971, статья «Исчисление высказываний».
3. ↑ ^{1 2} НФЭ, 2010.
4. ↑ ^{1 2 3} Герасимов, 2011, с. 13.
5. ↑ Войшвилло, Дегтярев, 2001, с. 91—94.
6. ↑ Эдельман, 1975, с. 130.
7. ↑ Эдельман, 1975, с. 128.
8. ↑ Игошин, 2008, с. 32.
9. ↑ ^{1 2} Герасимов, 2011, с. 17—19.
10. ↑ Герасимов, 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.

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

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

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

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

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

---