Пропозициональная формула

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

Формула высказываний строится из простых предложений , таких как «пять больше трех», или пропозициональных переменных, таких как P и Q , с использованием связок или логических операторов, таких как NOT, AND, OR или IMPLIES; Например:

( P, А НЕ Q ) ПОДРАЗУМЕВАЕТСЯ ( P ИЛИ Q ).

В математике , пропозициональная формула часто более кратко упоминаются как « предложение », но, что более точно, пропозициональная формула не является предложение , но формальное выражение , что означает на предложение , А формальный объект обсуждается, так же , как выражение такого поскольку « x + y » не является значением, а обозначает значение. В некоторых контекстах сохранение различия может иметь значение.

Предложения [ править ]

Для целей исчисления высказываний пропозиции (высказывания, предложения, утверждения) считаются простыми или сложными . ^[1] Сложные предложения считаются связанными сентенциальными связками , наиболее распространенными из которых являются «И», «ИЛИ», «ЕСЛИ… ТО…», «НИ… НИ…», «… ЭКВИВАЛЕНТНО… ". Связывающая точка с запятой «;» и связка «НО» считаются выражениями «И». Считается, что последовательность дискретных предложений связана с помощью «И», и формальный анализ применяет рекурсивное «правило скобок».по отношению к последовательности простых предложений (подробнее ниже о хорошо сформированные формулы).

Например: Утверждение: «Эта корова синего цвета. Эта лошадь оранжевая, а вот эта лошадь фиолетовая». на самом деле является составным утверждением, связанным с помощью "И": (("Эта корова синяя" И "эта лошадь оранжевая") И "эта лошадь фиолетовая").

Простые предложения декларативны по своей природе, то есть они делают утверждения о состоянии или природе конкретного объекта ощущения, например, «Эта корова синяя», «Это койот!» («Этот койот ЕСТЬ там , за скалами»). ^[2] Таким образом, простые «примитивные» утверждения должны относиться к конкретным объектам или определенным состояниям ума. У каждого должен быть как минимум подлежащее (непосредственный объект мысли или наблюдения), глагол (предпочтительно в активном голосе и в настоящем времени) и, возможно, прилагательное или наречие. "Собака!" вероятно, подразумевает «Я вижу собаку», но его следует отклонить как слишком двусмысленный.

Пример: «Эта фиолетовая собака бежит», «Эта корова синяя», «Коммутатор M31 закрыт», «Эта крышка снята», «Завтра пятница».

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

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

Исчисление предикатов идет на шаг дальше , чем исчислении к «анализу внутренней структуры суждений» ^[3] Это нарушает простое предложение на две части (я) его субъект (объект ( единственном или множественном числе) дискурса) и (ii) предикат (глагол или, возможно, предложение-глагол, которое утверждает качество или атрибут объекта (ов)). Затем исчисление предикатов обобщает форму «субъект | предикат» (где | символизирует конкатенацию (объединение) символов) в форму со следующей структурой пустой-субъект «___ | предикат», а предикат, в свою очередь, обобщается на все вещи с помощью это свойство.

Пример: «У этой синей свиньи есть крылья» превращается в два предложения в исчислении высказываний : «У этой свиньи есть крылья» И «Эта свинья синяя», внутренняя структура которой не рассматривается. Напротив, в исчислении предикатов первое предложение разбивается на «эта свинья» в качестве подлежащего и «имеет крылья» в качестве сказуемого. Таким образом, он утверждает, что объект «эта свинья» является членом класса (набора, коллекции) «крылатых вещей». Во втором предложении утверждается, что объект «эта свинья» имеет атрибут «синий» и, таким образом, является членом класса «синих вещей». Можно записать два предложения, связанных с И, как:

p | W И p | B

Обобщение «этой свиньи» на (потенциального) члена двух классов «крылатые предметы» и «синие предметы» означает, что у нее есть истинные отношения с обоими этими классами. Другими словами, для данной области дискурса «крылатые вещи» оказывается, что p либо является членом этой области, либо нет. Таким образом, существует связь W (крылатость) между p (свинья) и {T, F}, W (p) оценивается как {T, F}, где {T, F} - это набор логических значений «истина» и « ложный". Аналогично для B (голубизна) и p (свинья) и {T, F}: B (p) оценивается как {T, F}. Итак, теперь можно проанализировать связанные утверждения «B (p) AND W (p)» на предмет их общей истинностной ценности, то есть:

(B (p) AND W (p)) оценивается как {T, F}

В частности, простые предложения, в которых используются понятия «все», «некоторые», «несколько», «один из» и т. Д., Обрабатываются исчислением предикатов. Наряду с новым функциональным символизмом «F (x)» вводятся два новых символа: ∀ (для всех) и ∃ (существует ..., хотя бы один из ... существует и т. Д.). Исчисление предикатов, но не исчисление высказываний, может установить формальную справедливость следующего утверждения:

«У всех синих свиней есть крылья, но у некоторых свиней нет крыльев, поэтому некоторые свиньи не синие».

Личность [ править ]

Тарский утверждает, что понятие ИДЕНТИЧНОСТИ (в отличие от ЛОГИЧЕСКОЙ ЭКВИВАЛЕНТНОСТИ) лежит вне исчисления высказываний; однако он отмечает, что для того, чтобы логика была полезной для математики и наук, она должна содержать «теорию» ИДЕНТИЧНОСТИ. ^[4] Некоторые авторы ссылаются на «логику предикатов с идентичностью», чтобы подчеркнуть это расширение. Подробнее об этом ниже.

Алгебра предложений, исчисление высказываний [ править ]

Алгебра (и существует много различных них), свободно определяются, представляет собой способ , с помощью которого набор символов называется переменными вместе с некоторыми другими символами , такие как круглые скобки (,) и некоторое подмножеством символов , такими как *, +, \ , &, ∨, =, ≡, ∧, ￢ управляются в рамках системы правил. Считается, что эти символы и их правильно сформированные цепочки представляют объекты , но в конкретной алгебраической системе эти объекты не имеют значения . Таким образом, работа внутри алгебры становится упражнением в соблюдении определенных законов ( правил ) синтаксиса алгебры (формирования символов), а не всемантика (значение) символов. Смыслы следует искать вне алгебры.

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

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

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

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

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

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

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

Синтез : инженеры, в частности, синтезируют пропозициональные формулы (которые в конечном итоге превращаются в схемы символов) из таблиц истинности . Например, можно составить таблицу истинности того, как должно вести себя двоичное сложение при сложении переменных «b», «a» и «carry_in», «ci», и результатов «carry_out», «co» и «sum» Σ :

• Пример: в строке 5 ((b + a) + ci) = ((1 + 0) + 1) = число «2». записанное как двоичное число, это 10 ₂ , где «co» = 1 и Σ = 0, как показано в крайних правых столбцах.

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

Простейший тип пропозициональной формулы - пропозициональная переменная . Предложения, которые являются простыми ( атомарными ), символические выражения часто обозначаются переменными с именами p , q или P , Q и т. Д. Пропозициональная переменная предназначена для представления атомарного предложения (утверждения), например, «Сегодня суббота» = p (здесь символ = означает «… присвоена переменная с именем…») или «Я хожу в кино только в понедельник» = q .

Присваивание истинных ценностей, оценка формул [ править ]

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

Ценности истины в риторике, философии и математике : Ценности истины всего два: {ИСТИНА "T", ЛОЖЬ "F"}. An эмпиритика ставит все предложения на два больших класса: аналитическая -True независимо от того , какой (например тавтологию ), а также синтетические -derived из опыта и тем самым восприимчивым к подтверждению третьих сторон ( теория проверки смысла). ^[5] Эмпирики считают, что, как правило, достижение истинностной ценности синтетического предложения, значения (шаблоны сопоставления с образцом) должны быть сначала применены к словам, а затем эти шаблоны значений должны быть сопоставлены с тем, что утверждается. Например, мое высказывание "Эта корова синяя !" Это заявление ПРАВДА? Я действительно сказал это. А может быть , я буду видеть голубую корову, если только я не лгу мое утверждение является ИСТИНА относительно объекта моего (возможно , испорчено) восприятия. Но действительно ли синяя корова «там»? Что вы видите, когда смотрите в то же окно? Чтобы продолжить проверку, вам потребуется предварительное понятие (шаблон) как «корова», так и « синий », а также способность сопоставлять шаблоны с объектом ощущения (если он действительно существует). ^{[ необходима цитата ]}

Ценности истины в инженерии : инженеры стараются избегать представлений об истине и лжи, которые сбивают с толку философов, но в конечном итоге инженеры должны доверять своим измерительным приборам. В своем стремлении к надежности инженеры предпочитают извлекать известные объекты из небольшой библиотеки - объекты, которые имеют четко определенное, предсказуемое поведение даже в больших комбинациях (отсюда их название для исчисления высказываний: «комбинаторная логика»). Наименьшее количество вариантов поведения одного объекта - два (например, {OFF, ON}, {open, shut}, {UP, DOWN} и т. Д.), И они соответствуют {0, 1}. Такие элементы называются цифровыми ; те, у кого непрерывный диапазон поведения, называются аналоговыми. Всякий раз, когда необходимо принять решение в аналоговой системе, довольно часто инженер преобразует аналоговое поведение (дверь на 45,32146% UP) в цифровое (например, DOWN = 0) с помощью компаратора . ^[6]

Таким образом, назначение значений переменных и двух символов-значений {0, 1} происходит "извне" формулы, которая представляет поведение (обычно) составного объекта. Примером может служить дверь гаража с двумя «концевыми выключателями», один для UP, обозначенный SW_U, и один для DOWN, обозначенный SW_D, и все остальное, что есть в схеме двери. Осмотр схемы (либо схемы, либо самих объектов - двери, переключателей, проводов, печатной платы и т. Д.) Может выявить, что на печатной плате «узел 22» выходит на +0 В, когда контакты переключателя «SW_D» «механически соприкасаются (« закрыты ») и дверь находится в положении« вниз »(95% вниз), и« узел 29 »переходит в +0 В, когда дверь поднята на 95% и контакты переключателя SW_U находятся в механическом контакте («замкнуты»). ^[7]Инженер должен определить значения этих напряжений и все возможные комбинации (все 4 из них), включая «плохие» (например, оба узла 22 и 29 находятся под напряжением 0 вольт, что означает, что дверь открыта и закрыта одновременно). . Схема бездумно реагирует на любые напряжения, которые она испытывает, не осознавая ИСТИНУ или ЛОЖНОСТЬ, ПРАВИЛЬНО или НЕПРАВИЛЬНО, БЕЗОПАСНО или ОПАСНО. ^{[ необходима цитата ]}

Пропозициональные связки [ править ]

Произвольные пропозициональные формулы строятся из пропозициональных переменных и других пропозициональных формул с использованием пропозициональных связок . Примеры связок включают:

• Унарное отрицание связки. Если это формула, то это формула.${\ displaystyle \ alpha}$${\ Displaystyle \ lnot \ alpha}$
• Классические бинарные связки . Так, например, если и являются формулами, значит, и есть .${\ displaystyle \ land, \ lor, \ to, \ leftrightarrow}$${\ displaystyle \ alpha}$${\ displaystyle \ beta}$${\ Displaystyle (\ альфа \ к \ бета)}$
• Другие бинарные связки, такие как NAND, NOR и XOR
• Тернарная связка IF ... THEN ... ELSE ...
• Постоянные 0-арные связки ⊤ и ⊥ (поочередно, константы {T, F}, {1, 0} и т. Д.)
• Связка "теория-расширение" РАВНО (альтернативно, ИДЕНТИЧНОСТЬ или знак "=" в отличие от "логической связки" )${\ displaystyle \ leftrightarrow}$

Связки риторики, философии и математики [ править ]

Ниже приведены общие для риторики, философии и математики связки вместе с их таблицами истинности . Используемые символы будут варьироваться от автора к автору и от области деятельности. В общем, сокращения «T» и «F» обозначают оценки ИСТИНА и ЛОЖНОСТЬ, применяемые к переменным в формуле высказываний (например, утверждение: «Эта корова синяя» будет иметь истинностное значение «T» для Истины или « F "означает ложь, в зависимости от обстоятельств.)

Связки имеют несколько различных словосочетаний, например, «a ПОДРАЗУМЕВАЕТ b», также говорится «IF a THEN b». Некоторые из них показаны в таблице.

Инженерные связи [ править ]

В общем, инженерные связки такие же, как и математические связки, за исключением того, что они обычно оцениваются как «1» = «T» и «0» = «F». Это делается в целях анализа / минимизации и синтеза формул с использованием понятия минтермов и карт Карно (см. Ниже). Инженеры также используют слова логический продукт из понятия Буля (a * a = a) и логическая сумма из понятия Джевонса (a + a = a). ^[8]

CASE связка: IF… THEN… ELSE… [ править ]

IF ... THEN ... ELSE ... соединительно выглядит как простейшая форма СЛУЧАЙ оператор теории рекурсии и теория вычислений и является связка ответственности за условное Гото (прыжки, ветвь). Из этой одной связки могут быть построены все остальные связки (подробнее см. Ниже). Хотя фраза «IF c THEN b ELSE a» звучит как импликация, в наиболее сокращенной форме это переключатель, который принимает решение и предлагает в качестве результата только одну из двух альтернатив «a» или «b» (отсюда и название оператора switch на языке программирования C ). ^[9]

Следующие три предложения эквивалентны (на что указывает знак логической эквивалентности ≡):

1. (ЕСЛИ 'счетчик равен нулю' THEN 'перейти к инструкции b ' ELSE 'перейти к инструкции a ') ≡
2. ((c → b) & (~ c → a)) ≡ ((IF 'counter is zero' THEN 'перейти к инструкции b ') AND (IF 'Это НЕ тот случай, когда counter равен нулю' THEN 'перейти к инструкции а ) "≡
3. ((c & b) ∨ (~ c & a)) ≡ "('Счетчик равен нулю' И 'перейти к инструкции b ) ИЛИ (' Это НЕ тот случай, когда 'счетчик равен нулю' И 'перейти к инструкции a ) "

Таким образом, IF… THEN… ELSE - в отличие от импликации - не оценивается как двусмысленная «ИСТИНА», когда первое утверждение ложно, т.е. c = F in (c → b). Например, большинство людей отвергло бы следующее сложное предложение как бессмысленное non sequitur, потому что второе предложение не связано по значению с первым. ^[10]

Пример: утверждение «ЕСЛИ Уинстон Черчилль был китайцем, ТО« Солнце восходит на востоке »» оценивается как ИСТИНА, учитывая, что «Уинстон Черчилль был китайцем» - ЛОЖЬ, а «Солнце восходит на востоке» оценивается как ИСТИНА. .

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

Использование конструкции IF ... THEN ... ELSE позволяет избежать споров, поскольку она предлагает полностью детерминированный выбор между двумя заявленными альтернативами; он предлагает два «объекта» (две альтернативы b и a) и делает выбор между ними исчерпывающе и однозначно. ^[12] В приведенной ниже таблице истинности d1 - это формула: ((IF c THEN b) AND (IF NOT-c THEN a)). Его полностью сокращенная форма d2 - это формула: ((c AND b) OR (NOT-c AND a). Две формулы эквивалентны, как показано в столбцах «= d1» и «= d2». Инженеры-электрики называют полностью сокращенный формула оператора AND-OR-SELECT Оператор CASE (или SWITCH) является расширением той же идеи до n возможных, но взаимоисключающих результатов.Инженеры-электрики называют оператора CASE мультиплексором..

ИДЕНТИЧНОСТЬ и оценка [ править ]

Первая таблица этого раздела помечает *** запись логической эквивалентности, чтобы отметить тот факт, что « логическая эквивалентность » - это не то же самое, что «идентичность». Например, большинство согласятся, что утверждение «Эта корова синяя» идентично утверждению «Эта корова синяя». С другой стороны, в речи иногда появляется логическая эквивалентность, как в этом примере: «« Солнце светит »означает« я еду на велосипеде »». В переводе в пропозициональную формулу слова становятся: «ЕСЛИ 'солнце светит' ТОГДА ' Я катаюсь на велосипеде », И ЕСЛИ« Я катаюсь на велосипеде »ТОГДА« светит солнце »»: ^[13]

«IF 's' THEN 'b' AND IF 'b' THEN 's'» записывается как ((s → b) & (b → s)) или сокращенно как (s ↔ b). Поскольку крайняя правая строка символов является определением нового символа в терминах символов слева, использование знака ИДЕНТИЧНОСТЬ = является подходящим:

((s → b) & (b → s)) = (s ↔ b)

Разные авторы используют разные знаки для логической эквивалентности: ↔ (например, Суппес, Гудштейн, Гамильтон), ≡ (например, Роббин), ⇔ (например, Бендер и Уильямсон). Обычно идентичность записывается как знак равенства =. Одно исключение из этого правила находится в Principia Mathematica . Подробнее о философии понятия ИДЕНТИЧНОСТИ см . Закон Лейбница .

Как отмечалось выше, Тарский считает, что ИДЕНТИЧНОСТЬ лежит вне исчисления высказываний, но он утверждает, что без этого понятия «логика» недостаточна для математики и дедуктивных наук. Фактически, знак входит в исчисление высказываний, когда формула должна быть вычислена. ^[14]

В некоторых системах нет таблиц истинности, а есть только формальные аксиомы (например, строки символов из набора {~, →, (,), переменных p ₁ , p ₂ , p ₃ , ...} и правил формирования формул (правила о том, как сделать больше символьных строк из предыдущих строк, используя, например, подстановку и modus ponens ). Результатом такого исчисления будет другая формула (то есть правильно сформированная символьная строка). Однако в конце концов, если кто-то захочет При использовании исчисления для изучения понятий действительности и истины необходимо добавить аксиомы, которые определяют поведение символов, называемых «значениями истинности» {T, F} (или {1, 0} и т. д.), относительно других символов.

Например, Гамильтон использует два символа = и ≠, когда он определяет понятие оценки v любых правильно сформированных формул (wffs) A и B в своем «исчислении формальных утверждений» L. Оценка v - это функция от wffs выражения его система L соответствует диапазону (выходу) {T, F}, учитывая, что каждой переменной p ₁ , p ₂ , p ₃ в wff присваивается произвольное значение истинности {T, F}.

v ( A ) ≠ v (~ A )

( я )

v ( A → B ) = F тогда и только тогда, когда v ( A ) = T и v ( B ) = F

( ii )

Два определения ( i ) и ( ii ) определяют эквивалент таблиц истинности для связок ~ (НЕ) и → (ИМПЛИКАЦИЯ) его системы. Первый выводит F ≠ T и T ≠ F, другими словами « v ( A ) не означает v (~ A )». Определение ( ii ) задает третью строку в таблице истинности, а остальные три строки являются результатом применения определения ( i ). В частности ( ii ) присваивает значение F (или значение «F») всему выражению. Определения также служат в качестве правил формирования, которые позволяют заменять ранее полученное значение в формулу:

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

Более сложные формулы [ править ]

Как показано выше, связка CASE (IF c THEN b ELSE a) создается либо из связок с двумя аргументами IF ... THEN ... и AND, либо из OR, AND и 1-аргумента NOT. Соединительные элементы, такие как n-аргумент AND (a & b & c & ... & n), OR (a ∨ b ∨ c ∨ ... ∨ n), состоят из строк с двумя аргументами AND и OR и записываются в сокращенная форма без скобок. Эти и другие связки можно затем использовать в качестве строительных блоков для создания дополнительных связок. Риторики, философы и математики используют таблицы истинности и различные теоремы для анализа и упрощения своих формул.

Электротехника использует нарисованные символы и соединяет их линиями, обозначающими математический акт замещения и замены . Затем они сверяют свои рисунки с таблицами истинности и упрощают выражения, как показано ниже, с помощью карт Карно или теорем. Таким образом, инженеры создали множество «комбинаторной логики» (т. Е. Соединений без обратной связи), таких как «декодеры», «кодеры», «многофункциональные вентили», «мажоритарная логика», «двоичные сумматоры», «арифметические логические блоки», и т.п.

Определения [ править ]

Определение создает новый символ и его поведение, часто в целях сокращения. После того, как определение представлено, можно использовать любую форму эквивалентного символа или формулы. Следующий символизм = _Df следует соглашению Райхенбаха. ^[15] Несколько примеров удобных определений, взятых из набора символов {~, &, (,)} и переменных. Каждое определение порождает логически эквивалентную формулу, которую можно использовать для замены или замены.

• определение новой переменной: (c & d) = _Df s
• ИЛИ: ~ (~ a & ~ b) = _Df (a ∨ b)
• ПОСЛЕДСТВИЕ: (~ a ∨ b) = _Df (a → b)
• ИСКЛЮЧАЮЩЕЕ ИЛИ: (~ a & b) ∨ (a & ~ b) = _Df (a ⊕ b)
• ЛОГИЧЕСКАЯ ЭКВИВАЛЕНТНОСТЬ: ((a → b) & (b → a)) = _Df (a ≡ b)

Схемы аксиом и определений [ править ]

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

Пример: в определении (~ a ∨ b) = _Df (a → b) могут использоваться другие символы-переменные, такие как «SW2» и «CON1», то есть формально:

a = _Df SW2, b = _Df CON1, поэтому в качестве примера схемы определения (~ SW2 ∨ CON1) = _Df (SW2 → CON1)

Замена против замены [ править ]

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

Пример: (c & d) ∨ (p & ~ (c & ~ d)), но (q1 & ~ q2) ≡ d. Теперь везде, где встречается переменная "d", подставьте (q ₁ & ~ q ₂ ):

(c & (q ₁ & ~ q ₂ )) ∨ (p & ~ (c & ~ (q ₁ & ~ q ₂ )))

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

Пример: используйте этот набор схем / эквивалентов формул:

1. ((а ∨ 0) ≡ а).
2. ((a & ~ a) ≡ 0).
3. ((~ a ∨ b) = _Df (a → b)).
6. (~ (~ а) ≡ а)

1. начать с "а": а
2. Используйте 1, чтобы заменить "a" на (a 0): (a ∨ 0)
3. Используйте понятие «схема», чтобы заменить b на a в 2: ((a & ~ a)) 0)
4. Используйте 2, чтобы заменить 0 на (b & ~ b): (a ∨ (b & ~ b))
5. (см. ниже, как распределить "a ∨" по (b & ~ b) и т. д.)

Индуктивное определение [ править ]

Классическое представление логики высказываний (см. Enderton 2002) использует связки . Набор формул для данного набора пропозициональных переменных индуктивно определяется как наименьший набор выражений такой, что:${\ displaystyle \ lnot, \ land, \ lor, \ to, \ leftrightarrow}$

• Каждая пропозициональная переменная в наборе представляет собой формулу,
• ${\ Displaystyle (\ lnot \ альфа)}$формула всякий раз , когда есть, и${\ displaystyle \ alpha}$
• ${\ Displaystyle (\ альфа \, \ Коробка \, \ бета)}$является формулой всякий раз, когда и являются формулами, и является одной из бинарных связок .${\ displaystyle \ alpha}$${\ displaystyle \ beta}$${\ displaystyle \ Box}$${\ displaystyle \ land, \ lor, \ to, \ leftrightarrow}$

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

Индуктивное определение также можно перефразировать в терминах операции замыкания (Enderton 2002). Пусть V обозначает набор пропозициональных переменных, а X _V обозначает набор всех строк из алфавита, включая символы в V , левые и правые круглые скобки и все рассматриваемые логические связки. Каждая логическая связка соответствует операции построения формулы, функции от XX _V до XX _V :

• По заданной строке z операция возвращается .${\ Displaystyle {\ mathcal {E}} _ {\ lnot} (г)}$${\ Displaystyle (\ lnot г)}$
• Для заданных строк y и z операция возвращается . Есть аналогичные операции , и, соответствующие другим двоичным связкам.${\displaystyle {\mathcal {E}}_{\land }(y,z)}$${\displaystyle (y\land x)}$${\displaystyle {\mathcal {E}}_{\lor }}$${\displaystyle {\mathcal {E}}_{\to }}$${\displaystyle {\mathcal {E}}_{\leftrightarrow }}$

Набор формул над V определяется как наименьшее подмножество XX _V, содержащее V и закрытое для всех операций построения формулы.

Формулы синтаксического анализа [ править ]

Следующие «законы» исчисления высказываний используются для «сведения» сложных формул. «Законы» можно легко проверить с помощью таблиц истинности. Для каждого закона главная (самая внешняя) связка связана с логической эквивалентностью ≡ или тождеством =. Полный анализ всех 2 ⁿ комбинаций значений истинности для его n различных переменных приведет к столбцу единиц (Т) под этой связкой. Это открытие делает каждый закон по определению тавтологией. И для данного закона, поскольку его формулы слева и справа эквивалентны (или идентичны), они могут быть заменены друг на друга.

• Пример: Следующая таблица истинности является законом Де Моргана для поведения НЕ над ИЛИ: ~ (a ∨ b) ≡ (~ a & ~ b). Слева от главной связки ≡ (желтый столбец с надписью «туго натянутый») формула ~ (b ∨ a) оценивается как (1, 0, 0, 0) под меткой «P». Справа от «натянуто» формула (~ (b) ∨ ~ (a)) также оценивается как (1, 0, 0, 0) под меткой «Q». Поскольку два столбца имеют эквивалентные оценки, логическая эквивалентность ≡ под «натянутым» оценивается как (1, 1, 1, 1), то есть P ≡ Q. Таким образом, любая формула может быть заменена другой, если она появляется в более крупной формуле.

Предприимчивые читатели могут поставить перед собой задачу изобрести «аксиоматическую систему», которая использует символы {∨, &, ~, (,), переменные a, b, c}, правила формирования, указанные выше, и как можно меньше перечисленных законов. ниже, а затем вывести в виде теорем другие, а также оценки таблицы истинности для, & и ~. Один набор, приписываемый Хантингтону (1904) (Suppes: 204), использует восемь законов, определенных ниже.

При использовании в аксиоматической системе символы 1 и 0 (или T и F) считаются правильно построенными формулами и, таким образом, подчиняются всем тем же правилам, что и переменные. Таким образом, перечисленные ниже законы на самом деле являются схемами аксиом , то есть они заменяют бесконечное количество примеров. Таким образом, (x ∨ y) ≡ (y ∨ x) может использоваться в одном случае, (p ∨ 0) ≡ (0 ∨ p), а в другом случае (1 ∨ q) ≡ (q ∨ 1) и т. Д.

Соединительный стаж (символический ранг) [ править ]

В общем, чтобы избежать путаницы при анализе и оценке пропозициональных формул, широко используйте круглые скобки. Однако нередко авторы не учитывают их. Чтобы разобрать сложную формулу, сначала нужно знать старшинство или ранг , которые каждая из связок (за исключением *) имеет по сравнению с другими связками. Для того, чтобы «хорошо-форма» формула, начните с связкой с самим высоким рангом и добавить скобки вокруг его компонентов, а затем двигаться вниз по рангу (обращая особое внимание на соединителен в объем , над которым он работает). От самого старшего к старшему, с предикатными знаками ∀x и ∃x, ИДЕНТИЧНОСТЬ = и арифметические знаки добавлены для полноты: ^[16]

≡

(ЛОГИЧЕСКОЕ ЭКВИВАЛЕНТНОСТЬ)

→

(ПОСЛЕДСТВИЕ)

&

(И)

∨

(ИЛИ ЖЕ)

~

(НЕТ)

∀x

(ДЛЯ ВСЕХ x)

∃x

(ЕСТЬ СУЩЕСТВУЕТ x)

знак равно

(ЛИЧНОСТЬ)

+

(арифметическая сумма)

*

(арифметическое умножение)

'

(s, арифметический преемник).

Таким образом, формула может быть проанализирована, но поскольку NOT не подчиняется закону распределения, круглые скобки вокруг внутренней формулы (~ c & ~ d) являются обязательными:

Пример: "d & c ∨ w" переписывается как ((d & c) ∨ w)

Пример: «a & a → b ≡ a & ~ a ∨ b» переписано (строго) на

• ≡ имеет стаж: ((a & a → b) ≡ (a & ~ a ∨ b))
• → имеет стаж: ((a & (a → b)) ≡ (a & ~ a ∨ b))
• & имеет старшинство с обеих сторон: ((((a) & (a → b))) ≡ (((a) & (~ a ∨ b)))
• ~ имеет стаж: ((((a) & (a → b))) ≡ (((a) & (~ (a) ∨ b)))
• проверьте 9 (- скобки и 9) - скобки: ((((a) & (a → b))) ≡ (((a) & (~ (a) ∨ b)))

Пример:

d & c ∨ p & ~ (c & ~ d) ≡ c & d ∨ p & c ∨ p & ~ d переписано так (((d & c) ∨ (p & ~ ((c & ~ (d))) )) ≡ ((c & d) ∨ (p & c) ∨ (p & ~ (d))))

Коммутативные и ассоциативные законы [ править ]

И И, и ИЛИ подчиняются закону коммутативности и ассоциативному закону :

• Коммутативный закон для OR: (a ∨ b) ≡ (b ∨ a)
• Коммутативный закон для AND: (a & b) ≡ (b & a)
• Ассоциативный закон для ИЛИ: ((a ∨ b) ∨ c) ≡ (a ∨ (b ∨ c))
• Ассоциативный закон для AND: ((a & b) & c) ≡ (a & (b & c))

Отсутствие скобок в строках И и ИЛИ : связки считаются унарными (с одной переменной, например, НЕ) и двоичными (то есть с двумя переменными И, ИЛИ, ПОДРАЗУМЕВАЕТСЯ). Например:

((c & d) ∨ (p & c) ∨ (p & ~ d)) выше должно быть написано (((c & d) ∨ (p & c)) ∨ (p & ~ (d))) или, возможно, ((c & d) ∨ ((p & c) ∨ (p & ~ (d))))

Однако демонстрация таблицы истинности показывает, что форма без лишних скобок вполне подходит.

Отсутствие круглых скобок в отношении одиночной переменной НЕ : Хотя ~ (a), где a - единственная переменная, совершенно ясно, ~ a подходит и является обычным способом появления этого литерала . Когда НЕ ставится над формулой с более чем одним символом, скобки обязательны, например ~ (a ∨ b).

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

ИЛИ распределяет по И, а И распределяет по ИЛИ. НЕ распределяется по И или ИЛИ. См. Ниже о законе Де Моргана:

• Распределительный закон для OR: (c ∨ (a & b)) ≡ ((c ∨ a) & (c ∨ b))
• Распределительный закон для AND: (c & (a ∨ b)) ≡ ((c & a) ∨ (c & b))

Законы Де Моргана [ править ]

НЕ при распределении по ИЛИ или И делает что-то особенное (опять же, это можно проверить с помощью таблицы истинности):

• Закон Де Моргана для OR: ¬ (a ∨ b) ≡ (¬a ^ ¬b)
• Закон Де Моргана для AND: ¬ (a ^ b) ≡ (¬a ∨ ¬b)

Законы поглощения [ править ]

Поглощение, особенно первое, заставляет «законы» логики отличаться от «законов» арифметики:

• Поглощение (идемпотентность) для OR: (a ∨ a) ≡ a
• Поглощение (идемпотентность) для AND: (a & a) ≡ a

Законы оценки: идентичность, недействительность и дополнение [ править ]

Знак «=» (в отличие от логической эквивалентности ≡, поочередно ↔ или ⇔) символизирует присвоение значения или значения. Таким образом, строка (a & ~ (a)) символизирует "0", т. Е. Означает то же самое, что и символ "0" ". В некоторых" системах "это будет аксиома (определение), возможно, показанная как ((a & ~ (a)) = _Df 0); в других системах это может быть получено из приведенной ниже таблицы истинности:

• Коммутация равенства: (a = b) ≡ (b = a)
• Идентичность OR: (a ∨ 0) = a или (a ∨ F) = a
• Идентичность для AND: (a & 1) = a или (a & T) = a
• Обнуление для OR: (a ∨ 1) = 1 или (a ∨ T) = T
• Обнуление для AND: (a & 0) = 0 или (a & F) = F
• Дополнение для ИЛИ: (a ∨ ~ a) = 1 или (a ∨ ~ a) = T, закон исключенной середины
• Дополнение для AND: (a & ~ a) = 0 или (a & ~ a) = F, закон противоречия

Двойной отрицательный (инволюция) [ править ]

• ¬ (¬a) ≡ а

Правильные формулы (wffs) [ править ]

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

Индуктивное определение инфиксных формул в предыдущем разделе можно преобразовать в формальную грамматику в форме Бэкуса-Наура :

< формула >  :: =  < пропозициональная переменная >
| (¬ < формула > )| ( < формула > ∧ < формула > )| ( < формула > ∨ < формула > )| ( < формула > → < формула > )| ( < формула > ↔ < формула > )

Можно показать, что любое выражение, соответствующее грамматике, имеет сбалансированное количество левых и правых скобок, а любой непустой начальный сегмент формулы имеет больше левых, чем правых скобок. ^[17] Этот факт можно использовать для создания алгоритма разбора формул. Например, предположим, что выражение x начинается с . Начиная со второго символа, сопоставьте самое короткое подвыражение y из x, которое имеет сбалансированные круглые скобки. Если x - формула, после этого выражения остается ровно один символ, этот символ является закрывающей круглой скобкой, а y сам является формулой. Эту идею можно использовать для создания парсера рекурсивного спуска для формул.${\displaystyle (\lnot }$

Пример подсчета скобок :

Этот метод определяет как «1» главную связку - связку, под которой происходит общее вычисление формулы для крайних скобок (которые часто опускаются). ^[18] Он также определяет самую внутреннюю связку, с которой можно было бы начать вычисление формулы без использования таблицы истинности, например, на «уровне 6».

Правильно построенные формулы и действительные формулы в выводах [ править ]

Понятие действительного аргумента обычно применяется к умозаключениям в аргументах, но аргументы сводятся к пропозициональным формулам и могут быть оценены так же, как любая другая пропозициональная формула. Здесь действительный вывод означает: «Формула, которая представляет вывод, оценивается как« истина »ниже своей основной связки, независимо от того, какие истинностные значения присваиваются ее переменным», то есть формула является тавтологией. ^[19] Вполне возможно, что формула будет правильной, но недействительной . Другой способ сказать это: « Чтобы формула была действительной, необходимо быть хорошо сформированным, но этого недостаточно ». Единственный способ узнать, так ли этокак правильно сформированный, так и действительный - это подвергнуть его проверке с помощью таблицы истинности или с использованием «законов»:

• Пример 1. Что можно сказать о следующем утверждении, которому трудно следовать? Это действительно так? «Если солнечно, но если лягушка квакает, значит, не солнечно, то это все равно, что сказать, что лягушка не квакает». Преобразуйте это в пропозициональную формулу следующим образом:

  "ЕСЛИ (a И (ЕСЛИ b ТО НЕ-a) ТО НЕ-a", где "a" представляет "ее солнечный свет", а "b" представляет "лягушка квакает":

  (((a) & ((b) → ~ (a)) ≡ ~ (b))

  Это правильно, но действительно ли это ? Другими словами, при вычислении будет ли это давать тавтологию (все T) под символом логической эквивалентности ≡? Ответ НЕТ, это недействительно. Однако, если реконструирована как импликации , то аргумент является действительным.

  «Сказать, что солнечно, но если лягушка квакает, значит, не солнечно, значит , лягушка не квакает».

  Возможно, лягушка не квакает при других обстоятельствах: возможно, ее съел журавль.

• Пример 2 (от Райхенбаха через Бертрана Рассела):

  «Если у свиней есть крылья, некоторых крылатых животных можно есть. Некоторых крылатых животных можно есть, поэтому у свиней есть крылья».

  (((a) → (b)) & (b) → (a)) сформирован правильно, но недопустимый аргумент, как показано красной оценкой под основным импликацией:

Сокращенные наборы связок [ править ]

Набор логических связок называется полным, если каждая пропозициональная формула тавтологически эквивалентна формуле, содержащей только связки в этом наборе. Есть много комплектов связок, в том числе , и . Есть две бинарные связки, которые завершаются сами по себе, соответствующие NAND и NOR соответственно. ^[20] Например, некоторые пары неполные .${\displaystyle \{\land ,\lnot \}}$${\displaystyle \{\lor ,\lnot \}}$${\displaystyle \{\to ,\lnot \}}$${\displaystyle \{\land ,\lor \}}$

Ход (И-НЕ) [ править ]

Двоичная связка, соответствующая NAND, называется штрихом Шеффера и записывается с помощью вертикальной черты | или вертикальная стрелка ↑. Полнота этой связки была отмечена в Principia Mathematica (1927: xvii). Поскольку он сам по себе завершен, все остальные связки можно выразить только с помощью штриха. Например, где символ «≡» представляет собой логическую эквивалентность :

~ p ≡ p | p

р → д р | ~ д

p ∨ q ≡ ~ p | ~ q

p & q ≡ ~ (p | q)

В частности, нулевые связки (представляющие истину) и (представляющие ложь) могут быть выражены с помощью черты:${\displaystyle \top }$${\displaystyle \bot }$

${\displaystyle \top \equiv (a|(a|a))}$

${\displaystyle \bot \equiv (\top |\top )}$

ЕСЛИ… ТО… ИНАЧЕ [ править ]

Эта связка вместе с {0, 1}, (или {F, T} или { , }) образует полный набор. Далее соотношение IF ... THEN ... ELSE (c, b, a) = d представляет ((c → b) ∨ (~ c → a)) ≡ ((c & b) ∨ (~ c & а)) = d${\displaystyle \bot }$${\displaystyle \top }$

(в, б, а):

(c, 0, 1) ≡ ~ c

(c, b, 1) ≡ (c → b)

(c, c, a) ≡ (c ∨ a)

(c, b, c) ≡ (c и b)

Пример: Ниже показано, как будет проходить основанное на теореме доказательство «(c, b, 1) ≡ (c → b)», ниже доказательства - его проверка таблицы истинности. (Примечание: (c → b) определяется как (~ c ∨ b)):

• Начните с сокращенной формы: ((c & b) ∨ (~ c & a))
• Замените "1" на a: ((c & b) ∨ (~ c & 1))
• Идентичность (~ c & 1) = ~ c: ((c & b) ∨ (~ c))
• Закон коммутации для V: ((~ c) ∨ (c & b))
• Распределите "~ c V" по (c и b): (((~ c) ∨ c) & ((~ c) ∨ b)
• Закон исключенной середины (((~ c) ∨ c) = 1): ((1) & ((~ c) ∨ b))
• Распределите «(1) &» по ((~ c) ∨ b): (((1) & (~ c)) ∨ ((1) & b)))
• Коммутивность и идентичность ((1 & ~ c) = (~ c & 1) = ~ c, и ((1 & b) ≡ (b & 1) ≡ b: (~ c ∨ b)
• (~ c ∨ b) определяется как c → b QED

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

Нормальные формы [ править ]

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

Приведение к нормальной форме [ править ]

Приведение к нормальной форме относительно просто, если таблица истинности формулы подготовлена. Но дальнейшие попытки минимизировать количество литералов (см. Ниже) требуют некоторых инструментов: сокращение по законам Де Моргана и таблицам истинности может быть громоздким, но карты Карно очень подходят для небольшого числа переменных (5 или меньше). Некоторые сложные табличные методы существуют для более сложных схем с несколькими выходами, но они выходят за рамки данной статьи; подробнее см. алгоритм Куайна – Маккласки .

Буквальный, термин и альтернативный [ править ]

В электротехнике переменная x или ее отрицание ~ (x) объединяются в одно понятие, называемое литералом . Строка литералов, соединенных оператором AND, называется термином . Строка литералов, соединенных ИЛИ, называется альтермом . Обычно литерал ~ (x) сокращается до ~ x. Иногда символ & вообще опускается в порядке алгебраического умножения.

• Примеры
  1. a, b, c, d - переменные. (((a & ~ (b)) & ~ (c)) & d) - это термин. Это может быть сокращенно (a & ~ b & ~ c & d) или a ~ b ~ cd.
  2. p, q, r, s - переменные. (((p & ~ (q)) & r) & ~ (s)) - это альтернатива. Это может быть сокращено как (p ∨ ~ q ∨ r ∨ ~ s).

Minterms [ править ]

Точно так же, как таблица истинности из 2 ⁿ строк отображает оценку пропозициональной формулы для всех 2 ⁿ возможных значений ее переменных, n переменных создает 2 ⁿ -квадратную карту Карно (даже если мы не можем нарисовать ее полностью). размерная реализация). Например, 3 переменные дают 2 ³ = 8 строк и 8 квадратов Карно; 4 переменные дают 16 строк таблицы истинности и 16 квадратов и, следовательно, 16 минтермов . Каждый квадрат карты Карно и соответствующая ему оценка таблицы истинности представляют один минтерм.

Любая пропозициональная формула может быть сведена к «логической сумме» (ИЛИ) активных (т. Е. Со значением «1» или «Т») терминов. Говорят, что в этой форме формула имеет дизъюнктивную нормальную форму . Но даже несмотря на то, что он находится в этой форме, он не обязательно минимизирован ни по количеству терминов, ни по количеству литералов.

В следующей таблице обратите внимание на особую нумерацию строк: (0, 1, 3, 2, 6, 7, 5, 4, 0). Первый столбец является десятичным эквивалентом двоичного эквивалента цифр «cba», другими словами:

• Пример

  cba ₂ = c * 2 ² + b * 2 ¹ + a * 2 ⁰ :

  cba = (c = 1, b = 0, a = 0) = 101 ₂ = 1 * 2 ² + 0 * 2 ¹ + 1 * 2 ⁰ = 5 ₁₀

Такая нумерация возникает из-за того, что при перемещении по таблице от строки к строке только одна переменная за раз меняет свое значение. Код Грея является производным от этого понятия. Это понятие может быть расширено до трехмерных и четырехмерных гиперкубов, называемых диаграммами Хассе, где переменные каждого угла изменяются только по одной за раз при перемещении по краям куба. Диаграммы Хассе (гиперкубы), сплющенные в два измерения, являются либо диаграммами Вейча, либо картами Карно (это практически одно и то же).

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

Сокращение с использованием метода карты (Veitch, Karnaugh) [ править ]

Вейч улучшил понятие диаграмм Венна , преобразовав круги в прилегающие квадраты, а Карно упростил диаграмму Вейча, преобразовав минтермы, записанные в их буквальной форме (например, ~ abc ~ d), в числа. ^[21] Метод работает следующим образом:

Составьте таблицу истинности формулы [ править ]

Составьте таблицу истинности формулы. Пронумеруйте его строки, используя двоичные эквиваленты переменных (обычно просто последовательно от 0 до n-1) для n переменных.

Технически пропозициональная функция была сведена к ее (неминимизированной) конъюнктивной нормальной форме: каждая строка имеет свое выражение minterm, и их можно объединить с помощью ИЛИ, чтобы получить формулу в ее (неминимизированной) конъюнктивной нормальной форме.

Пример: ((c & d) ∨ (p & ~ (c & (~ d)))) = q в конъюнктивной нормальной форме:

((~ p & d & c) ∨ (p & d & c) ∨ (p & d & ~ c) ∨ (p & ~ d & ~ c)) = q

Однако эта формула может быть уменьшена как по количеству членов (с 4 до 3), так и по общему количеству ее литералов (с 12 до 6).

Создайте карту Карно формулы [ править ]

Используйте значения формулы (например, «p»), найденные методом таблицы истинности, и поместите их в их соответствующие (связанные) квадраты Карно (они пронумерованы в соответствии с соглашением о кодах Грея). Если в таблице появляются значения «d» для «безразлично», это добавляет гибкости на этапе сокращения.

Уменьшить minterms [ править ]

Минтермы соседних (примыкающих) 1-квадратов (Т-квадратов) могут быть уменьшены относительно количества их литералов , и числовые члены также будут уменьшены в процессе. Два примыкающих квадрата (2 x 1 по горизонтали или 1 x 2 по вертикали, даже края представляют собой примыкающие квадраты) теряют один буквальный, четыре квадрата в прямоугольнике 4 x 1 (горизонтальном или вертикальном) или квадрате 2 x 2 (даже четыре угла представляют примыкающие друг к другу квадраты) теряют два литерала, восемь квадратов в прямоугольнике теряют 3 литерала и т. д. (Один ищет самый большой квадрат или прямоугольники и игнорирует меньшие квадраты или прямоугольники, полностью содержащиеся в нем.) Этот процесс продолжается до тех пор, пока не будут учтены все примыкающие квадраты, в этот момент пропозициональная формула сводится к минимуму.

Например, квадраты №3 и №7 упираются. Эти два смежных квадрата могут потерять один литерал (например, «p» из квадратов №3 и №7), четыре квадрата в прямоугольнике или квадрате теряют два литерала, восемь квадратов в прямоугольнике теряют 3 литерала и т. Д. (Один ищет самый большой квадрат или прямоугольники.) Этот процесс продолжается до тех пор, пока не будут учтены все примыкающие квадраты, после чего формула высказывания считается минимизированной.

Пример: метод карты обычно выполняется путем осмотра. Следующий пример расширяет алгебраический метод, чтобы показать «трюк», стоящий за объединением терминов на карте Карно:

Минтермы № 3 и № 7 упираются, № 7 и № 6 упираются, а № 4 и № 6 упираются (потому что края стола огибают). Таким образом, каждая из этих пар может быть сокращена.

Обратите внимание, что по закону идемпотентности (A ∨ A) = A мы можем создать больше терминов. Тогда по законам ассоциации и распределения исчезающие переменные могут быть объединены в пары, а затем «исчезнут» с Законом противоречия (x & ~ x) = 0. Далее скобки [и] используются только для отслеживания терминов; они не имеют особого значения:

• Приведите формулу в соединительную нормальную форму с сокращаемой формулой:

q = ((~ p & d & c) ∨ (p & d & c) ∨ (p & d & ~ c) ∨ (p & ~ d & ~ c)) = (# 3 ∨ # 7 ∨ # 6 ∨ # 4)

• Идемпотентность (поглощение) [A ∨ A) = A:

(# 3 ∨ [# 7 ∨ # 7] ∨ [# 6 ∨ # 6] ∨ # 4)

• Ассоциативный закон (x ∨ (y ∨ z)) = ((x ∨ y) ∨ z)

([# 3 ∨ # 7] ∨ [# 7 ∨ # 6] ∨ [# 6 ∨ # 4])

[ (~ p & d & c) ∨ (p & d & c) ] ∨ [ (p & d & c) ∨ (p & d & ~ c) ] ∨ [ (p & d & ~ c) ∨ (p & ~ d & ~ c) ] .

• Распределительный закон (x & (y ∨ z)) = ((x & y) ∨ (x & z)):

([(d & c) ∨ (~ p & p)] ∨ [(p & d) ∨ (~ c & c)] ∨ [(p & ~ c) ∨ (c & ~ c)])

• Коммутативный закон и закон противоречия (x & ~ x) = (~ x & x) = 0:

([(d & c) ∨ (0)] ∨ [(p & d) ∨ (0)] ∨ [(p & ~ c) ∨ (0)])

• Закон тождества (x ∨ 0) = x, приводящий к сокращенной форме формулы:

q = ((d & c) ∨ (p & d) ∨ (p & ~ c))

Проверьте редукцию с помощью таблицы истинности [ править ]

Неопровержимые предложения [ править ]

Учитывая следующие примеры-как-определения, что можно сделать с последующими рассуждениями:

(1) «Это простое предложение». (2) «Это сложное предложение, соединенное с помощью AND».

Затем присвойте переменную «s» самому левому предложению «Это простое предложение». Определите "составное" c = "not simple" ~ s и присвойте c = ~ s к "Это предложение является составным"; присвоить «j» значение «Оно [это предложение] соединено оператором AND». Второе предложение можно выразить так:

(НЕ (а) И j)

Если значения истинности должны быть помещены в предложения c = ~ s и j, то все они явно ЛОЖНЫ: например, «Это сложное предложение» - это ЛОЖЬ (это просто по определению). Итак, их союз (И) - ложь. Но в собранном виде предложение - ИСТИНА.

Это пример парадоксов , возникающих в результате непредикативного определения, то есть, когда объект m имеет свойство P, но объект m определяется в терминах свойства P. ^[22] Лучший совет для ритора или вовлеченного лица в дедуктивном анализе следует избегать непредикативных определений, но в то же время внимательно следить за ними, потому что они действительно могут создавать парадоксы. С другой стороны, инженеры заставляют их работать в форме пропозициональных формул с обратной связью.

Формула предложения с «обратной связью» [ править ]

Понятие пропозициональной формулы, появляющейся как одна из собственных переменных, требует правила формирования, которое позволяет присваивать формулу переменной. В общем, нет никаких условий (как аксиоматические системы, так и системы таблиц истинности объектов и отношений), которые запрещали бы это происходить. ^[23]

Самый простой случай возникает, когда формула ИЛИ становится одним из собственных входов, например, p = q. Начнем с (p ∨ s) = q, затем пусть p = q. Заметьте, что «определение» q зависит от самого «q», а также от «s» и связки ИЛИ; это определение q, таким образом, не является предикативным . Результатом может быть одно из двух условий: ^[24] колебание или память.

Это помогает думать о формуле как о черном ящике . Без знания того, что происходит «внутри» формулы - «коробки» извне, могло бы казаться, что выход больше не является функцией только входов. То есть, иногда кто-то смотрит на q и видит 0, а иногда 1. Чтобы избежать этой проблемы, нужно знать состояние (условие) «скрытой» переменной p внутри блока (то есть значение q, возвращенное и присвоенное п). Когда это известно, очевидное несоответствие исчезает.

Чтобы понять [предсказать] поведение формул с обратной связью, требуется более сложный анализ последовательных цепей . Формулы высказываний с обратной связью в своей простейшей форме приводят к конечным автоматам; они также приводят к воспоминаниям в виде лент Тьюринга и счетчиков контрмашины. Из сочетания этих элементов можно построить любой вид ограниченной расчетной модели (например , машины Тьюринга , встречные машины , регистрировать машины , компьютеры Macintosh и т.д.).

Колебание [ править ]

В абстрактном (идеальном) случае простейшая осциллирующая формула - это НЕ, возвращаемое самому себе: ~ (~ (p = q)) = q. Анализ абстрактной (идеальной) пропозициональной формулы в таблице истинности обнаруживает несоответствие как для случаев p = 1, так и для p = 0: когда p = 1, q = 0, этого не может быть, потому что p = q; то же самое для случаев, когда p = 0 и q = 1.

Колебание с задержкой : если задержка ^[25] (идеальная или неидеальная) вставлена ​​в абстрактную формулу между p и q, тогда p будет колебаться между 1 и 0: 101010 ... 101 ... до бесконечности . Если задержка и НЕ являются абстрактными (т. Е. Не идеальными), тип анализа, который будет использоваться, будет зависеть от точной природы объектов, составляющих осциллятор; такие вещи выходят за рамки математики и инженерии.

Анализ требует, чтобы была вставлена ​​задержка, а затем разрыв цикла между задержкой и входом «p». Задержку следует рассматривать как своего рода предложение, в котором «qd» (с задержкой q) является выходом, а «q» - входом. Это новое предложение добавляет еще один столбец в таблицу истинности. Несоответствие теперь между «qd» и «p», как показано красным; два стабильных состояния, в результате чего:

Память [ править ]

Без промедления необходимо устранить несоответствия из анализа таблицы истинности. С понятием «задержка» это условие представляет собой мгновенное несоответствие между выходной переменной q обратной связи и _{задержкой} p = q .

Таблица истинности показывает строки, в которых возникают несоответствия между p = q, _{задержанным} на входе, и q на выходе. После «нарушения» обратной связи ^[26] построение таблицы истинности продолжается обычным образом. Но после этого в каждой строке вывод q сравнивается с теперь независимым вводом p, и отмечаются любые несоответствия между p и q (т. Е. P = 0 вместе с q = 1 или p = 1 и q = 0); когда «линия» «переделывается», то и то и другое становится невозможным по Закону противоречия ~ (p & ~ p)). Строки, показывающие несоответствия, либо считаются переходными состояниями, либо просто удаляются как несогласованные и, следовательно, «невозможные».

Однажды перевернутая память [ править ]

О простейших результатах памяти, когда выход ИЛИ возвращается на один из его входов, в этом случае выход «q» возвращается в «p». Учитывая, что формула сначала вычисляется (инициализируется) с p = 0 и q = 0, она «перевернется» один раз, когда «установлена» на s = 1. После этого выход «q» будет поддерживать «q» в «перевернутом» состоянии (состояние q = 1). Это поведение, теперь зависящее от времени, показано на диаграмме состояний справа от однократного переворота.

Триггер памяти [ править ]

Следующий простейший случай - это триггер «установка-сброс», показанный под однократным триггером. Учитывая, что r = 0 & s = 0 и q = 0 в начале, он «устанавливается» (s = 1) аналогично однократному переворачиванию. Однако он имеет возможность «сбросить» q = 0, когда «r» = 1. И дополнительные сложности возникают, если и set = 1, и reset = 1. В этой формуле set = 1 вынуждает выход q = 1, поэтому, когда и если (s = 0 & r = 1), триггер будет сброшен. Или, если (s = 1 & r = 0) будет установлен триггер. В абстрактном (идеальном) примере, в котором одновременно s = 1 ⇒ s = 0 & r = 1 ⇒ r = 0, формула q будет неопределенной (неразрешимой). Из-за задержек в «реальном» ИЛИ, И и НЕ результат будет изначально неизвестен, но впоследствии предсказуем.

Память с синхронизацией триггеров [ править ]

Формула, известная как «синхронизированная память триггера» («c» - это «часы», а «d» - «данные»), приведена ниже. Это работает следующим образом: когда c = 0, данные d (0 или 1) не могут «пройти», чтобы повлиять на выход q. Когда c = 1, данные d «проходят», а выход q «следует» за значением d. Когда c изменяется от 1 до 0, последнее значение данных остается "захваченным" на выходе "q". Пока c = 0, d может изменять значение, не вызывая изменения q.

• Примеры
  1. ((c & d) ∨ ( p & (~ (c & ~ (d)))) = q , но теперь пусть p = q:
  2. ((c & d) ∨ ( q & (~ (c & ~ (d)))) = q

Диаграмма состояний похожа по форме на диаграмму состояний триггера, но с другой маркировкой на переходах .

Историческое развитие [ править ]

Бертран Рассел (1912: 74) перечисляет три закона мысли, которые происходят от Аристотеля : (1) Закон тождества : «Все, что есть, есть», (2) Закон непротиворечивости : «Ничто не может одновременно быть и не быть». и (3) Закон исключенного третьего : «Все должно быть или не быть».

• Пример: Здесь O - выражение о БЫТИИ или КАЧЕСТВЕ объекта:
  1. Закон идентичности: O = O
  2. Закон противоречия: ~ (O & ~ (O))
  3. Закон исключенной середины: (O ∨ ~ (O))

Использование слова «все» в законе исключенного третьего делает выражение этого закона Расселом открытым для обсуждения. Если ограничиться выражением о БЫТИИ или КАЧЕСТВЕ применительно к конечному набору объектов (конечной «вселенной дискурса»), члены которой можно исследовать один за другим на предмет наличия или отсутствия утверждения, - тогда закон считается интуитивно уместным. Таким образом, утверждение типа: «Этот объект должен БЫТЬ или НЕ БЫТЬ (в коллекции)» или «Этот объект должен либо иметь это КАЧЕСТВО, либо НЕ иметь это КАЧЕСТВО (относительно объектов в коллекции)» является приемлемым. См. Больше на диаграмме Венна .

Хотя исчисление высказываний возникло у Аристотеля, понятие алгебры, примененное к предложениям, пришлось отложить до начала 19 века. В (неблагоприятной) реакции на 2000 год традиции Аристотеля силлогизмов , Джон Локк «s Эссе относительно человеческого понимания (1690) использовал слово семиотика (теория использования символов). К 1826 году Ричард Уэйтли критически проанализировал силлогистическую логику с симпатией к семиотике Локка. Работа Джорджа Бентама (1827 г.) привела к появлению понятия «количественная оценка предиката» (1827 г.) (в настоящее время обозначается как ∀ ≡ «для всех»). "Ссора", спровоцированная Уильямом Гамильтономпо поводу приоритетного спора с Августом Де Морганом "вдохновил Джорджа Буля написать свои идеи по логике и опубликовать их как MAL [Mathematical Analysis of Logic] в 1847 году" (Grattin-Guinness and Bornet 1997: xxviii).

О своем вкладе комментируют Граттин-Гиннесс и Борнет:

«Основным единственным нововведением Буля был [] закон [x ⁿ = x] для логики: он гласил, что мысленные действия по выбору свойства x и повторному выбору x аналогичны выбору x один раз ... он сформировал уравнения x • (1-x) = 0 и x + (1-x) = 1, которые для него выражали соответственно закон противоречия и закон исключенного третьего »(стр. xxviiff). Для Буля «1» было вселенной дискурса, а «0» - ничем.

Масштабное начинание Готтлоба Фреге (1879 г.) привело к формальному исчислению предложений, но его символика настолько устрашающа, что не оказала большого влияния, за исключением одного человека: Бертрана Рассела . Сначала, будучи учеником Альфреда Норта Уайтхеда, он изучил работу Фреге и предложил (известную и печально известную) поправку к ней (1904 г.) вокруг проблемы антиномии, которую он обнаружил в трактовке Фреге (см . Парадокс Рассела ). Работа Рассела привела к сотрудничеству с Уайтхедом, который в 1912 году выпустил первый том Principia Mathematica.(ВЕЧЕРА). Именно здесь впервые появилась то, что мы считаем «современной» логикой высказываний. В частности, PM вводит НЕ и ИЛИ, а также символ утверждения ⊦ как примитивы. В терминах этих понятий они определяют ИМПЛИКАЦИЯ → (по умолчанию * 1.01: ~ p ∨ q), затем И (по умолчанию * 3.01: ~ (~ p ∨ ~ q)), затем ЭКВИВАЛЕНТНОСТЬ p ← → q (* 4.01: ( p → q) & (q → p)).

• Генри М. Шеффер (1921) и Жан Никод демонстрируют, что только одна связка, «штрих» | достаточно, чтобы выразить все пропозициональные формулы.
• Эмиль Пост (1921) развивает метод анализа таблицы истинности в своем «Введении в общую теорию элементарных предложений». Он отмечает инсульт Никода | .
• Уайтхед и Рассел добавляют введение к своему переизданию ПМ в 1927 году, частично добавляя благоприятное отношение к «инсульту».

Вычислительная и коммутационная логика :

• Уильям Экклс и Ф. У. Джордан (1919) описывают «пусковое реле», сделанное из электронной лампы.
• Джордж Стибиц (1937) изобретает двоичный сумматор, используя механические реле. Он строит это на своем кухонном столе.

Пример: даны двоичные биты a _i и b _i и перенос (c_in _i ), их сумма Σ _i и перенос (c_out _i ):

• ((a _i XOR b _i ) XOR c_in _i ) = Σ _i
• (a _i и b _i ) ∨ c_in _i ) = c_out _i ;

• Алан Тьюринг построил множитель, используя реле (1937–1938). Для этого ему нужно вручную намотать катушки реле.
• Учебники по «коммутационным схемам» появляются в начале 1950-х годов.
• Уиллард Куайн 1952 и 1955, EW Veitch 1952 и M. Karnaugh (1953) разрабатывают методы отображения для упрощения пропозициональных функций.
• Джордж Х. Мили (1955) и Эдвард Ф. Мур (1956) обращаются к теории последовательных (т. Е. С коммутационной схемой) «машин».
• Э. Дж. Маккласки и Х. Шорр разработали метод упрощения пропозициональных (коммутационных) схем (1962).

Сноски [ править ]

Ссылки [ править ]

• Бендер, Эдвард А. и Уильямсон, С. Гилл , 2005 г., Краткий курс дискретной математики , Dover Publications, Mineola NY, ISBN 0-486-43946-1 . Этот текст используется в «двухквартальном курсе по информатике» в Калифорнийском университете в Сан-Диего. 
• Enderton, HB , 2002, Математическое введение в логику. Harcourt / Academic Press. ISBN 0-12-238452-0 
• Гудштейн, Р.Л. , (Pergamon Press 1963), 1966, (Dover edition 2007), Boolean Algebra , Dover Publications, Inc. Минола, Нью-Йорк, ISBN 0-486-45894-6 . Акцент на понятие «алгебра классов» с теоретико-множественными символами, такими как, ∪, '(НЕ), ⊂ (СЛЕДУЕТ). Позже Гольдштейн заменяет их на &, ∨, ￢, → (соответственно) в своей трактовке «Логики предложений», стр. 76–93. 
• Айвор Граттан-Гиннесс и Жерар Борне 1997, Джордж Буль: Избранные рукописи по логике и ее философии , Birkhäuser Verlag, Basil, ISBN 978-0-8176-5456-6 (Бостон). 
• А.Г. Гамильтон, 1978, логика для математиков , Cambridge University Press, Кембридж, Великобритания, ISBN 0-521-21838-1 . 
• EJ McCluskey 1965, Введение в теорию коммутационных цепей , McGraw-Hill Book Company, Нью-Йорк. Нет ISBN. Номер карточки каталога Библиотеки Конгресса 65-17394. Маккласки был учеником Уилларда Куайна и разработал некоторые известные теоремы вместе с Куайном и самостоятельно. Для тех, кто интересуется историей, книга содержит множество ссылок.
• Марвин Л. Мински 1967, Вычисления: конечные и бесконечные машины , Prentice-Hall, Inc., Englewood Cliffs, NJ. Нет ISBN. Номер карточки каталога Библиотеки Конгресса 67-12342. Особенно полезно для вычислимости, а также для хороших источников.
• Пол С. Розенблум 1950, Дуврское издание 2005, Элементы математической логики , Dover Publications, Inc., Минеола, Нью-Йорк, ISBN 0-486-44617-4 . 
• Джоэл В. Роббин 1969, 1997, « Математическая логика: первый курс» , Dover Publications, Inc., Минеола, Нью-Йорк, ISBN 0-486-45018-X (pbk.). 
• Патрик Суппес 1957 (издание Dover 1999 г.), Введение в логику , Dover Publications, Inc., Минеола, Нью-Йорк. ISBN 0-486-40687-3 (PBK). Эта книга уже напечатана и легко доступна. 
• На своей странице 204 в сноске он ссылается на свой набор аксиом на EV Huntington , "Наборы независимых постулатов для алгебры логики", Transactions of the American Mathematical Society, Vol. 5 91904), с. 288-309.
• Альфред Тарски 1941 (издание Dover 1995), Введение в логику и методологию дедуктивных наук , Dover Publications, Inc., Минеола, Нью-Йорк. ISBN 0-486-28462-X (PBK). Эта книга уже напечатана и легко доступна. 
• Жан ван Хейеноорт 1967, 3-е издание с поправками 1976, От Фреге до Гёделя: Справочник по математической логике, 1879-1931 , Издательство Гарвардского университета, Кембридж, Массачусетс. ISBN 0-674-32449-8 (pbk.) Можно найти перевод / перепечатку Фреге (1879), письма Рассела Фреге (1902) и письма Фреге Расселу (1902), парадокса Ричарда (1905), Поста (1921). здесь. 
• Альфред Норт Уайтхед и Бертран Рассел, 1927 г., 2-е издание, издание в мягкой обложке * 53, 1962 г., Principia Mathematica , Cambridge University Press, без ISBN. В период между первым изданием 1912 года и вторым изданием 1927 года HM Sheffer 1921 и M. Jean Nicod (год не указан) обратили внимание Рассела и Уайтхеда на то, что то, что они считали своими примитивными предложениями (связками), можно свести к single |, в настоящее время известное как "ход" или И-НЕ (НЕ-И, НИКОГДА ... НИ ...). Рассел-Уайтхед обсуждает это в своем «Введении ко второму изданию» и дает определения, как обсуждалось выше.
• Уильям Э. Викес 1968, « Логический дизайн с интегральными схемами» , John Wiley & Sons, Inc., Нью-Йорк. Нет ISBN. Номер карточки каталога Библиотеки Конгресса: 68-21185. Подробное изложение инженерных методов анализа и синтеза, ссылается на McCluskey 1965. В отличие от Суппеса, представление Уикса «булевой алгебры» начинается с набора постулатов, имеющих характер таблицы истинности, а затем выводится из них обычные теоремы (стр. 18ff).

Внешние ссылки [ править ]

• СМИ, связанные с формулой высказываний на Викискладе?