Тавтология в логике – Тавтология (логика) — Википедия

Тавтология (логика) — Википедия

Материал из Википедии — свободной энциклопедии

У этого термина существуют и другие значения, см. Тавтология.

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

Тот факт, что формула A — тавтология, обозначается ⊨A{\displaystyle \vDash A}. В каждом логическом исчислении имеется своё множество тавтологий.

Построение тавтологий

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

Примеры тавтологий

Тавтологии исчисления высказываний (и алгебры высказываний)

• A→A{\displaystyle A\rightarrow A} («Из A следует A») — закон тождества
• (A)∨(¬A){\displaystyle (A)\lor (\lnot A)} («A или не-A») — закон исключённого третьего
• ¬(P∧¬P){\displaystyle \neg (P\land \neg P)} — закон отрицания противоречия
• ¬¬P→P{\displaystyle \neg \neg P\rightarrow P} — закон двойного отрицания
• (P↔Q)↔(¬Q↔¬P){\displaystyle (P\leftrightarrow Q)\leftrightarrow (\neg Q\leftrightarrow \neg P)} — закон противоположности
• (P∧Q)↔(Q∧P){\displaystyle (P\land Q)\leftrightarrow (Q\land P)} — коммутативность конъюнкции
• (P∨Q)↔(Q∨P){\displaystyle (P\lor Q)\leftrightarrow (Q\lor P)} — коммутативность дизъюнкции
• [(P∧Q)∧R]↔[P∧(Q∧R){\displaystyle [(P\land Q)\land R]\leftrightarrow [P\land (Q\land R)} — ассоциативность конъюнкции
• [(P∨Q)∨R]↔[P∨(Q∨R)]{\displaystyle [(P\lor Q)\lor R]\leftrightarrow [P\lor (Q\lor R)]} — ассоциативность дизъюнкции
• (P∧(P→Q))→Q{\displaystyle (P\land (P\rightarrow Q))\rightarrow Q}
• A→(B→A){\displaystyle A\rightarrow (B\rightarrow A)} (истина следует из чего угодно)
• A↔¬¬A{\displaystyle A\leftrightarrow \neg \neg A} (закон двойного отрицания)
• (A→B)∧(B→C)→(A→C){\displaystyle (A\rightarrow B)\wedge (B\rightarrow C)\rightarrow (A\rightarrow C)} — правило цепного заключения
• (A∨B)∧C↔(A∧C)∨(B∧C){\displaystyle (A\vee B)\wedge C\leftrightarrow (A\wedge C)\vee (B\wedge C)} — дистрибутивность конъюнкции относительно дизъюнкции
• (A∧B)∨C↔(A∨C)∧(B∨C){\displaystyle (A\wedge B)\vee C\leftrightarrow (A\vee C)\wedge (B\vee C)} — дистрибутивность дизъюнкции относительно конъюнкции
• (P∧P)↔P{\displaystyle (P\land P)\leftrightarrow P} — идемпотентность конъюнкции
• (P∨P)↔P{\displaystyle (P\lor P)\leftrightarrow P} — идемпотентность дизъюнкции
• (P→Q)↔(¬P∨Q){\displaystyle (P\rightarrow Q)\leftrightarrow (\neg P\lor Q)}
• (P↔Q)↔((P↔Q)∧(Q↔P)){\displaystyle (P\leftrightarrow Q)\leftrightarrow ((P\leftrightarrow Q)\land (Q\leftrightarrow P))}
• (P∧(Q∨P)↔P{\displaystyle (P\land (Q\lor P)\leftrightarrow P} — первый закон поглощения
• (P∨(Q∧P)↔P{\displaystyle (P\lor (Q\land P)\leftrightarrow P} — второй закон поглощения
• ¬(A∧B)↔(¬A∨¬B){\displaystyle \neg (A\wedge B)\leftrightarrow (\neg A\vee \neg B)} — первый закон де Моргана
• ¬(A∨B)↔(¬A∧¬B){\displaystyle \neg (A\vee B)\leftrightarrow (\neg A\wedge \neg B)} — второй закон де Моргана
• (A→B)↔(¬B→¬A){\displaystyle (A\rightarrow B)\leftrightarrow (\neg B\rightarrow \neg A)} — закон контрапозиции
• Если ⊨F(X1,…,Xn){\displaystyle \vDash F(X_{1},…,X_{n})} и h2,…,Hn{\displaystyle H_{1},…,H_{n}} — формулы, то ⊨F(h2,…,Hn){\displaystyle \vDash F(H_{1},…,H_{n})} (правило подстановки)

Тавтологии исчисления предикатов (и алгебры предикатов)

• Если F(X1,…,Xn){\displaystyle F(X_{1},…,X_{n})} — тавтология в исчислении высказываний и P1,…,Pn{\displaystyle P_{1},…,P_{n}} — предикаты, то F(P1,…,Pn){\displaystyle F(P_{1},…,P_{n})} — тавтология в исчислении предикатов
• ¬(∀x)P(x)↔(∃x)¬P(x){\displaystyle \neg (\forall x)P(x)\leftrightarrow (\exists x)\neg P(x)}

¬(∃x)P(x)↔(∀x)¬P(x){\displaystyle \neg (\exists x)P(x)\leftrightarrow (\forall x)\neg P(x)} (закон де Моргана)

• (∀x)(P(x)∧Q(x))↔(∀x)P(x)∧(∀x)Q(x){\displaystyle (\forall x)(P(x)\wedge Q(x))\leftrightarrow (\forall x)P(x)\wedge (\forall x)Q(x)}
• (∃x)(P(x)∨Q(x))↔(∃x)P(x)∨(∃x)Q(x){\displaystyle (\exists x)(P(x)\vee Q(x))\leftrightarrow (\exists x)P(x)\vee (\exists x)Q(x)}
• Q↔(∃x)Q{\displaystyle Q\leftrightarrow (\exists x)Q}
• Q↔(∀x)Q{\displaystyle Q\leftrightarrow (\forall x)Q}
• (∀x)P(x)→P(y){\displaystyle (\forall x)P(x)\rightarrow P(y)}
• P(y)→(∃x)P(x){\displaystyle P(y)\rightarrow (\exists x)P(x)}
• (∀x)(∀y)P(x,y)↔(∀y)(∀x)P(x,y){\displaystyle (\forall x)(\forall y)P(x,y)\leftrightarrow (\forall y)(\forall x)P(x,y)}
• (∃x)(∃y)P(x,y)↔(∃y)(∃x)P(x,y){\displaystyle (\exists x)(\exists y)P(x,y)\leftrightarrow (\exists y)(\exists x)P(x,y)}
• (∃x)(∀y)P(x,y)→(∀y)(∃x)P(x,y){\displaystyle (\exists x)(\forall y)P(x,y)\rightarrow (\forall y)(\exists x)P(x,y)}

Пример тавтологии в литературе

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

Формализуем его:

X{\displaystyle X} — играет в хоккей

M{\displaystyle M} — настоящий мужчина

¬X{\displaystyle \lnot X} — не играет в хоккей

¬M{\displaystyle \lnot M} — не настоящий мужчина (трус)

Получаем формулу:

(X→M)→(¬M→¬X){\displaystyle (X\rightarrow M)\rightarrow (\lnot M\rightarrow \lnot X)}

которая является логической тавтологией.

См. также

Примечания

Литература

• Игошин В. И. «Математическая логика и теория алгоритмов». — Academia, 2008.
• Карпов Ю. Г. «Теория автоматов». — П., 2003.— С. 49, 60.
• Мендельсон Э. «Введение в математическую логику». — М. Наука, 1971.
• Игошин В. И. «Задачник -практикум по математической логике». — Просвещение, 1986.

wikipedia.green

§ 5. Логические тавтологии

В обычном языке слово «тавтология» означает повторение того, что уже было сказано: «Жизнь есть жизнь» или «Не повезет так не повезет».

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

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

Французский капитан Ла Паллис пал в битве при Павии в 1525 г. В его честь солдаты сложили дошедшую до наших дней песню «За четверть часа до смерти он был еще живой…». Понятая буквально, эта строка песни, ставшая ее названием, является тавтологией. Как таковая она совершенно пуста. Всякий человек до самой своей смерти жив. Сказать о ком-то, что он был жив за день до своей смерти или за четверть часа до нее, значит, ровным счетом ничего о нем не сказать.

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

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

С легкой руки Л.Витгенштейна слово «тавтология» стало широко использоваться для характеристики законов логики.

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

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

Например, в формулу «А или не-А», представляющую закон исключенного третьего, вместо переменной А должны подставляться высказывания, т.е. выражения языка, являющиеся истинными или ложными. Результаты таких постановок: «Дождь идет или не идет», «Два плюс два равно нулю или не равно нулю», «Бог существует или его нет» и тому подобное. Каждое из этих сложных высказываний является истинным. И какие бы дальнейшие высказывания ни подставлялись вместо А — как истинные, так и ложные, — результат будет тем же — полученное высказывание будет истинным.

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

Ошибочные истолкования логических тавтологий

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

Из тавтологии «Дождь идет или не идет» мы ничего не можем узнать о погоде. Тавтология «Неверно, что бог есть и его нет» ровным счетом ничего не говорит о существовании бога. Ни одна тавтология не несет содержательной информации о мире.

Тавтология не описывает никакого реального положения вещей. Она совместима с любым таким положением. Немыслима ситуация, сопоставлением с которой можно было бы тавтологию опровергнуть.

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

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

Действительно ли законы логики не несут никакой информации?

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

Мысль об информационной пустоте логических законов является, конечно, ошибочной. В основе ее лежит крайне узкое истолкование опыта, способного подтверждать научные утверждения и законы. Этот опыт сводится к фрагментарным, изолированным ситуациям или фактам. Они достаточны для проверки истинности элементарных описательных утверждений типа «Идет дождь» или «Я иду быстро». Но явно недостаточны для суждения об истинности абстрактных теоретических обобщений, опирающихся не на отдельные разрозненные факты, а на совокупный, систематический опыт. Даже законы опытных наук, подобных биологии или физике, нельзя обосновать простой ссылкой на факты и конкретику. Тем более это невозможно сделать в случае самых абстрактных из всех законов — законов логики. Они должны черпать свое обоснование из предельно широкого опыта мыслительной, теоретической деятельности. За законами логики стоит, конечно, опыт, и в этом они сходны со всеми научными законами. Но опыт не в форме каких-то изолированных, доступных наблюдению ситуаций, а конденсированный опыт всей истории человеческого познания.

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

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

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

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

Литература

Бочаров В.А. Логика. — М., 1993.

Горский Д.П., Ивин А.А., Никифоров А.Л. Краткий словарь по логике. — М., 1991.

Ивин А. А. Строгий мир логики. — М., 1988.

Ивин А. А. Элементарная логика. — М., 1994.

Ивлев Ю. В . Логика. — М., 1992.

Карри  Х.Б. Основания математической логики. — М., 1969.

Клини  С.К. Математическая логика. — М., 1973.

Новиков П.С. Элементы математической логики. — М., 1973.

Черч А. Введение в математическую логику. — Т.1. — М., 1960.

Контрольные вопросы

В чем опасность логических противоречий?

Какие возражения выдвигаются против закона противоречия?

На чем основываются сомнения в универсальности закона исключенного третьего?

Какие неправильные умозаключения смешиваются обычно с модусом поненсом и модусом толленсом?

В чем ошибочность концепции «основных» законов логики?

Что такое логическая тавтология?

Означает ли тавтологический характер законов логики их априорность?

Темы рефератов и докладов

Понятие логического закона

Закон противоречия и споры вокруг него

Закон исключенного третьего

Законы логики как тавтологии

Логическое следование

Несостоятельность теории «основных» законов логики

Природа логических законов

studfiles.net

ЛОГИЧЕСКИЕ ТАВТОЛОГИИ. По законам логики

ЛОГИЧЕСКИЕ ТАВТОЛОГИИ

В обычном языке слово «тавтология» означает повторение того, что уже было сказано; «Жизнь есть жизнь» или «Не повезет так не повезет».

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

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

Французский капитан Ла Паллис пал в битве при Павии в 1525 году. В его честь солдаты сложили дошедшую до наших дней песню «За четверть часа до смерти он был еще живой…». Понятая буквально, эта строка песни, ставшая ее названием, является тавтологией. Как таковая она совершенно пуста. Всякий человек до самой своей смерти жив. Сказать о ком-то, что он был жив за день до своей смерти или за четверть часа до нее, значит, ровным счетом ничего о нем не сказать.

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

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

С легкой руки Л. Витгенштейна слово «тавтология» стало широко использоваться для характеристики законов логики.

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

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

Например, в формулу «А или не-А», представляющую закон исключенного третьего, вместо переменной А должны подставляться высказывания, то есть выражения языка, являющиеся истинными или ложными. Результаты таких подстановок: «Дождь идет или не идет», «Два плюс два равно нулю или не равно нулю», «Бог существует или его нет» и тому подобное. Каждое из этих сложных высказываний является истинным. И какие бы дальнейшие высказывания ни подставлялись вместо А — как истинные, так и ложные, — результат будет тем же — полученное высказывание будет истинным.

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

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

Из тавтологии «Дождь идет или не идет» мы ничего не можем узнать о погоде. Тавтология «Неверно, что бог есть и его нет» ровным счетом ничего не говорит о существовании бога. Ни одна тавтология не несет содержательной информации о мире.

Тавтология не описывает никакого реального положения вещей. Она совместима с любым таким положением. Немыслима ситуация, сопоставлением с которой можно было бы тавтологию опровергнуть.

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

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

Действительно ли законы логики не несут никакой информации?

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

Мысль об информационной пустоте логических законов является, конечно, ошибочной. В основе ее лежит крайне узкое истолкование опыта, способного подтверждать научные утверждения и законы. Этот опыт сводится к фрагментарным, изолированным ситуациям или фактам. Они достаточны для проверки истинности элементарных описательных утверждений типа «Идет дождь» или «Я иду быстро». Но явно недостаточны для суждения об истинности абстрактных теоретических обобщений, опирающихся не на отдельные, разрозненные факты, а на совокупный, систематический опыт. Даже законы опытных наук, подобных биологии или физике, нельзя обосновать простой ссылкой на факты и конкретику. Тем более это невозможно сделать в случае самых абстрактных из всех законов — законов логики. Они должны черпать свое обоснование из предельно широкого опыта мыслительной, теоретической деятельности. За законами логики стоит, конечно, опыт, и в этом они сходны со всеми иными научными законами. Но опыт не в форме каких-то изолированных, доступных наблюдению ситуаций, а конденсированный опыт всей истории человеческого познания.

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

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

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

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

Поделитесь на страничке

Следующая глава >

fil.wikireading.ru

§2. Формулы алгебры логики. Тавтологии.

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

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

Определение 1: Формулами исчисления высказываний являются:

а) каждая пропозиционная буква;

б) если и— формулы, то формулами являются также,,,,,.

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

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

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

Так, например, выражение является формулой, в которой все скобки можно опустить. А в выражениискобки опускать нельзя.

Определение 2: Формулы исчисления высказываний, образованные из пропозиционных букв ,,…, , логических операций и скобок, будем обозначать. Если в этой формуле заменить пропозиционные буквы,,…, соответственно высказываниями,,…,, то получим составное высказывание, которое назовёмлогическим значением формулы при , ,…, .

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

л	л	л	и	и	и
л	л	и	и	и	и
л	и	л	и	и	и
л	и	и	и	и	и
и	л	л	и	л	и
и	л	и	и	и	и
и	и	л	л	л	л
и	и	и	л	и	и

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

Определение 3: Формула исчисления высказываний называется тавтологией (или тождественно истинной формулой), если её значения есть «истина» для всех наборов значений пропозиционных переменных, входящих в эту формулу.

Нахождение тавтологий – это основная задача логики высказываний, так как они выражают законы логического мышления.

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

Теорема 1: Следующие формулы исчисления высказываний являются тавтологиями:

1) —закон исключенного третьего;

2) —закон отрицания противоречия;

3) —закон двойного отрицания;

4) ,

5) ,

6) ,

7) —законы упрощения;

8) ,

9) —законы коммутативности конъюнкции и дизъюнкции;

10) ,

11) —законы ассоциативности операций и;

12) ,

13) —законы дистрибутивности;

14) ,

15) —законы де Моргана;

16) —закон тождества;

17) —закон контрапозиции;

18) —правило цепного заключения;

19) ,

20) ,

21) —свойства рефлексивности, симметричности и транзитивности операции ↔ соответственно;

22) —закон противоречия.

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

Докажем некоторые из перечисленных тавтологий.

(1) Действительно, по определению отрицания, для любого высказывания , либо оно, либо его отрицание истинно. И, следовательно, дизъюнкцияистинна, т. к. одна из её компонент обязательно будет истинной. Первое утверждение теоремы доказано.

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

(14) Пусть и – два высказывания. Рассмотрим два составных высказывания и. Допустим, что отрицаниеистинно. Тогда конъюнкциябудет ложна, а, следовательно, по крайней мере, одно из высказыванийили ложно. Но тогда, по крайней мере, одно из высказываний или– истинно, а, следовательно, их дизъюнкциятоже истинна.

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

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

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

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

Определение 5: Формула исчисления высказываний называется выполнимой, если существует такой набор значений пропозиционных переменных, входящих в эту формулу, при котором формула принимает значение «истина».

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

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

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

studfiles.net

Тавтология (логика) — Википедия. Что такое Тавтология (логика)

Материал из Википедии — свободной энциклопедии

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

Тот факт, что формула A — тавтология, обозначается ⊨A{\displaystyle \vDash A}. В каждом логическом исчислении имеется своё множество тавтологий.

Построение тавтологий

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

Примеры тавтологий

Тавтологии исчисления высказываний (и алгебры высказываний)

• A→A{\displaystyle A\rightarrow A} («Из A следует A») — закон тождества
• (A)∨(¬A){\displaystyle (A)\lor (\lnot A)} («A или не-A») — закон исключённого третьего
• ¬(P∧¬P){\displaystyle \neg (P\land \neg P)} — закон отрицания противоречия
• ¬¬P→P{\displaystyle \neg \neg P\rightarrow P} — закон двойного отрицания
• (P↔Q)↔(¬Q↔¬P){\displaystyle (P\leftrightarrow Q)\leftrightarrow (\neg Q\leftrightarrow \neg P)} — закон противоположности
• (P∧Q)↔(Q∧P){\displaystyle (P\land Q)\leftrightarrow (Q\land P)} — коммутативность конъюнкции
• (P∨Q)↔(Q∨P){\displaystyle (P\lor Q)\leftrightarrow (Q\lor P)} — коммутативность дизъюнкции
• [(P∧Q)∧R]↔[P∧(Q∧R){\displaystyle [(P\land Q)\land R]\leftrightarrow [P\land (Q\land R)} — ассоциативность конъюнкции
• [(P∨Q)∨R]↔[P∨(Q∨R)]{\displaystyle [(P\lor Q)\lor R]\leftrightarrow [P\lor (Q\lor R)]} — ассоциативность дизъюнкции
• (P∧(P→Q))→Q{\displaystyle (P\land (P\rightarrow Q))\rightarrow Q}
• A→(B→A){\displaystyle A\rightarrow (B\rightarrow A)} (истина следует из чего угодно)
• A↔¬¬A{\displaystyle A\leftrightarrow \neg \neg A} (закон двойного отрицания)
• (A→B)∧(B→C)→(A→C){\displaystyle (A\rightarrow B)\wedge (B\rightarrow C)\rightarrow (A\rightarrow C)} — правило цепного заключения
• (A∨B)∧C↔(A∧C)∨(B∧C){\displaystyle (A\vee B)\wedge C\leftrightarrow (A\wedge C)\vee (B\wedge C)} — дистрибутивность конъюнкции относительно дизъюнкции
• (A∧B)∨C↔(A∨C)∧(B∨C){\displaystyle (A\wedge B)\vee C\leftrightarrow (A\vee C)\wedge (B\vee C)} — дистрибутивность дизъюнкции относительно конъюнкции
• (P∧P)↔P{\displaystyle (P\land P)\leftrightarrow P} — идемпотентность конюнкции
• (P∨P)↔P{\displaystyle (P\lor P)\leftrightarrow P} — идемпотентность дизъюнкции
• (P→Q)↔(¬P∨Q){\displaystyle (P\rightarrow Q)\leftrightarrow (\neg P\lor Q)}
• (P↔Q)↔((P↔Q)∧(Q↔P)){\displaystyle (P\leftrightarrow Q)\leftrightarrow ((P\leftrightarrow Q)\land (Q\leftrightarrow P))}
• (P∧(Q∨P)↔P{\displaystyle (P\land (Q\lor P)\leftrightarrow P} — первый закон поглощения
• (P∨(Q∧P)↔P{\displaystyle (P\lor (Q\land P)\leftrightarrow P} — второй закон поглощения
• ¬(A∧B)↔(¬A∨¬B){\displaystyle \neg (A\wedge B)\leftrightarrow (\neg A\vee \neg B)} — первый закон де Моргана
• ¬(A∨B)↔(¬A∧¬B){\displaystyle \neg (A\vee B)\leftrightarrow (\neg A\wedge \neg B)} — второй закон де Моргана
• (A→B)↔(¬B→¬A){\displaystyle (A\rightarrow B)\leftrightarrow (\neg B\rightarrow \neg A)} — закон контрапозиции
• Если ⊨F(X1,…,Xn){\displaystyle \vDash F(X_{1},…,X_{n})} и h2,…,Hn{\displaystyle H_{1},…,H_{n}} — формулы, то ⊨F(h2,…,Hn){\displaystyle \vDash F(H_{1},…,H_{n})} (правило подстановки)

Тавтологии исчисления предикатов (и алгебры предикатов)

• Если F(X1,…,Xn){\displaystyle F(X_{1},…,X_{n})} — тавтология в исчислении высказываний и P1,…,Pn{\displaystyle P_{1},…,P_{n}} — предикаты, то F(P1,…,Pn){\displaystyle F(P_{1},…,P_{n})} — тавтология в исчислении предикатов
• ¬(∀x)P(x)↔(∃x)¬P(x){\displaystyle \neg (\forall x)P(x)\leftrightarrow (\exists x)\neg P(x)}

¬(∃x)P(x)↔(∀x)¬P(x){\displaystyle \neg (\exists x)P(x)\leftrightarrow (\forall x)\neg P(x)} (закон де Моргана)

• (∀x)(P(x)∧Q(x))↔(∀x)P(x)∧(∀x)Q(x){\displaystyle (\forall x)(P(x)\wedge Q(x))\leftrightarrow (\forall x)P(x)\wedge (\forall x)Q(x)}
• (∃x)(P(x)∨Q(x))↔(∃x)P(x)∨(∃x)Q(x){\displaystyle (\exists x)(P(x)\vee Q(x))\leftrightarrow (\exists x)P(x)\vee (\exists x)Q(x)}
• Q↔(∃x)Q{\displaystyle Q\leftrightarrow (\exists x)Q}
• Q↔(∀x)Q{\displaystyle Q\leftrightarrow (\forall x)Q}
• (∀x)P(x)→P(y){\displaystyle (\forall x)P(x)\rightarrow P(y)}
• P(y)→(∃x)P(x){\displaystyle P(y)\rightarrow (\exists x)P(x)}
• (∀x)(∀y)P(x,y)↔(∀y)(∀x)P(x,y){\displaystyle (\forall x)(\forall y)P(x,y)\leftrightarrow (\forall y)(\forall x)P(x,y)}
• (∃x)(∃y)P(x,y)↔(∃y)(∃x)P(x,y){\displaystyle (\exists x)(\exists y)P(x,y)\leftrightarrow (\exists y)(\exists x)P(x,y)}
• (∃x)(∀y)P(x,y)→(∀y)(∃x)P(x,y){\displaystyle (\exists x)(\forall y)P(x,y)\rightarrow (\forall y)(\exists x)P(x,y)}

Пример тавтологии в литературе

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

Формализуем его:

X{\displaystyle X} — играет в хоккей

M{\displaystyle M} — настоящий мужчина

¬X{\displaystyle \lnot X} — не играет в хоккей

¬M{\displaystyle \lnot M} — не настоящий мужчина (трус)

Получаем формулу:

(X→M)→(¬M→¬X){\displaystyle (X\rightarrow M)\rightarrow (\lnot M\rightarrow \lnot X)}

которая является логической тавтологией.

См. также

Примечания

Литература

• Игошин В. И. «Математическая логика и теория алгоритмов». — Academia, 2008.
• Карпов Ю. Г. «Теория автоматов». — П., 2003.— С. 49, 60.
• Мендельсон Э. «Введение в математическую логику». — М. Наука, 1971.
• Игошин В. И. «Задачник -практикум по математической логике». — Просвещение, 1986.

wiki.sc

Тавтология (логика) Википедия

У этого термина существуют и другие значения, см. Тавтология.

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

Тот факт, что формула A — тавтология, обозначается ⊨A{\displaystyle \vDash A}. В каждом логическом исчислении имеется своё множество тавтологий.

Построение тавтологий

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

Примеры тавтологий

Тавтологии исчисления высказываний (и алгебры высказываний)

• A→A{\displaystyle A\rightarrow A} («Из A следует A») — закон тождества
• (A)∨(¬A){\displaystyle (A)\lor (\lnot A)} («A или не-A») — закон исключённого третьего
• ¬(P∧¬P){\displaystyle \neg (P\land \neg P)} — закон отрицания противоречия
• ¬¬P→P{\displaystyle \neg \neg P\rightarrow P} — закон двойного отрицания
• (P↔Q)↔(¬Q↔¬P){\displaystyle (P\leftrightarrow Q)\leftrightarrow (\neg Q\leftrightarrow \neg P)} — закон противоположности
• (P∧Q)↔(Q∧P){\displaystyle (P\land Q)\leftrightarrow (Q\land P)} — коммутативность конъюнкции
• (P∨Q)↔(Q∨P){\displaystyle (P\lor Q)\leftrightarrow (Q\lor P)} — коммутативность дизъюнкции
• [(P∧Q)∧R]↔[P∧(Q∧R)]{\displaystyle [(P\land Q)\land R]\leftrightarrow [P\land (Q\land R)]} — ассоциативность конъюнкции
• [(P∨Q)∨R]↔[P∨(Q∨R)]{\displaystyle [(P\lor Q)\lor R]\leftrightarrow [P\lor (Q\lor R)]} — ассоциативность дизъюнкции
• (P∧(P→Q))→Q{\displaystyle (P\land (P\rightarrow Q))\rightarrow Q}
• A→(B→A){\displaystyle A\rightarrow (B\rightarrow A)} (истина следует из чего угодно)
• A↔¬¬A{\displaystyle A\leftrightarrow \neg \neg A} (закон двойного отрицания)
• (A→B)∧(B→C)→(A→C){\displaystyle (A\rightarrow B)\wedge (B\rightarrow C)\rightarrow (A\rightarrow C)} — правило цепного заключения
• (A∨B)∧C↔(A∧C)∨(B∧C){\displaystyle (A\vee B)\wedge C\leftrightarrow (A\wedge C)\vee (B\wedge C)} — дистрибутивность конъюнкции относительно дизъюнкции
• (A∧B)∨C↔(A∨C)∧(B∨C){\displaystyle (A\wedge B)\vee C\leftrightarrow (A\vee C)\wedge (B\vee C)} — дистрибутивность дизъюнкции относительно конъюнкции
• (P∧P)↔P{\displaystyle (P\land P)\leftrightarrow P} — идемпотентность конъюнкции
• (P∨P)↔P{\displaystyle (P\lor P)\leftrightarrow P} — идемпотентность дизъюнкции
• (P→Q)↔(¬P∨Q){\displaystyle (P\rightarrow Q)\leftrightarrow (\neg P\lor Q)}
• (P↔Q)↔((P↔Q)∧(Q↔P)){\displaystyle (P\leftrightarrow Q)\leftrightarrow ((P\leftrightarrow Q)\land (Q\leftrightarrow P))}
• (P∧(Q∨P)↔P{\displaystyle (P\land (Q\lor P)\leftrightarrow P} — первый закон поглощения
• (P∨(Q∧P)↔P{\displaystyle (P\lor (Q\land P)\leftrightarrow P} — второй закон поглощения
• ¬(A∧B)↔(¬A∨¬B){\displaystyle \neg (A\wedge B)\leftrightarrow (\neg A\vee \neg B)} — первый закон де Моргана
• ¬(A∨B)↔(¬A∧¬B){\displaystyle \neg (A\vee B)\leftrightarrow (\neg A\wedge \neg B)} — второй закон де Моргана
• (A→B)↔(¬B→¬A){\displaystyle (A\rightarrow B)\leftrightarrow (\neg B\rightarrow \neg A)} — закон контрапозиции
• Если ⊨F(X1,…,Xn){\displaystyle \vDash F(X_{1},…,X_{n})} и h2,…,Hn{\displaystyle H_{1},…,H_{n}} — формулы, то ⊨F(h2,…,Hn){\displaystyle \vDash F(H_{1},…,H_{n})} (правило подстановки)

Тавтологии исчисления предикатов (и алгебры предикатов)

• Если F(X1,…,Xn){\displaystyle F(X_{1},…,X_{n})} — тавтология в исчислении высказываний и P1,…,Pn{\displaystyle P_{1},…,P_{n}} — предикаты, то F(P1,…,Pn){\displaystyle F(P_{1},…,P_{n})} — тавтология в исчислении предикатов
• ¬(∀x)P(x)↔(∃x)¬P(x){\displaystyle \neg (\forall x)P(x)\leftrightarrow (\exists x)\neg P(x)}

¬(∃x)P(x)↔(∀x)¬P(x){\displaystyle \neg (\exists x)P(x)\leftrightarrow (\forall x)\neg P(x)} (закон де Моргана)

• (∀x)(P(x)∧Q(x))↔(∀x)P(x)∧(∀x)Q(x){\displaystyle (\forall x)(P(x)\wedge Q(x))\leftrightarrow (\forall x)P(x)\wedge (\forall x)Q(x)}
• (∃x)(P(x)∨Q(x))↔(∃x)P(x)∨(∃x)Q(x){\displaystyle (\exists x)(P(x)\vee Q(x))\leftrightarrow (\exists x)P(x)\vee (\exists x)Q(x)}
• Q↔(∃x)Q{\displaystyle Q\leftrightarrow (\exists x)Q}
• Q↔(∀x)Q{\displaystyle Q\leftrightarrow (\forall x)Q}
• (∀x)P(x)→P(y){\displaystyle (\forall x)P(x)\rightarrow P(y)}
• P(y)→(∃x)P(x){\displaystyle P(y)\rightarrow (\exists x)P(x)}
• (∀x)(∀y)P(x,y)↔(∀y)(∀x)P(x,y){\displaystyle (\forall x)(\forall y)P(x,y)\leftrightarrow (\forall y)(\forall x)P(x,y)}
• (∃x)(∃y)P(x,y)↔(∃y)(∃x)P(x,y){\displaystyle (\exists x)(\exists y)P(x,y)\leftrightarrow (\exists y)(\exists x)P(x,y)}
• (∃x)(∀y)P(x,y)→(∀y)(∃x)P(x,y){\displaystyle (\exists x)(\forall y)P(x,y)\rightarrow (\forall y)(\exists x)P(x,y)}

Пример тавтологии в литературе

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

Формализуем его:

X{\displaystyle X} — играет в хоккей

M{\displaystyle M} — настоящий мужчина

¬X{\displaystyle \lnot X} — не играет в хоккей

¬M{\displaystyle \lnot M} — не настоящий мужчина (трус)

Получаем формулу:

(X→M)→(¬M→¬X){\displaystyle (X\rightarrow M)\rightarrow (\lnot M\rightarrow \lnot X)}

которая является логической тавтологией.

См. также

Примечания

Литература

• Игошин В. И. «Математическая логика и теория алгоритмов». — Academia, 2008.
• Карпов Ю. Г. «Теория автоматов». — П., 2003.— С. 49, 60.
• Мендельсон Э. «Введение в математическую логику». — М. Наука, 1971.
• Игошин В. И. «Задачник -практикум по математической логике». — Просвещение, 1986.

wikiredia.ru

Тавтология (логика) • ru.knowledgr.com

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

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

Формула выполнима, если это верно по крайней мере под одной интерпретацией, и таким образом тавтология — формула, отрицание которой невыполнимо. Невыполнимые заявления, и через отрицание и через подтверждение, известны формально как противоречия. Формула, которая не является ни тавтологией, ни противоречием, как говорят, логически случайна. Такая формула может быть сделана или верная или ложная основанной на ценностях, назначенных на его логические переменные. Двойное примечание турникета используется, чтобы указать, что S — тавтология. Тавтология иногда символизируется «Vpq» и противоречием «Opq». Символ мишени иногда используется, чтобы обозначить произвольную тавтологию с двойным символом (falsum) представление произвольного противоречия.

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

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

История

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

В 1800 Иммануэль Кант написал в своей книге Логика:

: «Идентичность понятий в аналитических суждениях может быть или явной (explicita) или неявной (implicita). В прежнем случае аналитические суждения тавтологические».

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

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

В 1921, в его Tractatus Logico-Philosophicus, Людвиг Витгенштейн предложил, чтобы заявления, которые могут быть выведены логическим вычитанием, были тавтологическими (пустой от значения), а также быть аналитическими истинами. Анри Пуанкаре сделал подобные замечания в Науке и Гипотезе в 1905. Хотя Бертран Рассел сначала привел доводы против этих замечаний Витгенштейном и Пойнкэре, утверждая, что математические истины не были только нетавтологическими, но и были синтетическим продуктом, он позже говорил в пользу них в 1918:

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

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

В течение 1930-х была развита формализация семантики логической логики с точки зрения назначений правды. Семестр тавтология начал применяться к тем логическим формулам, которые верны независимо от правды или ошибочности их логических переменных. Некоторые ранние книги по логике (такие как Символическая Логика К. Ай. Льюисом и Лэнгфордом, 1932) использовали термин для любого суждения (в любой формальной логике), который универсально действителен. Распространено в представлениях после этого (таких как Стивен Клини 1967 и Герберт Эндертон 2002) использовать тавтологию, чтобы относиться к логически действительной логической формуле, но поддержать различие между тавтологией и логически действительный в контексте логики первого порядка (см. ниже).

Фон

Логическая логика начинается с логических переменных, атомные единицы, которые представляют конкретные суждения. Формула состоит из логических переменных, связанных логическими соединительными словами значащим способом, так, чтобы правда полной формулы могла быть уникально выведена из правды или ошибочности каждой переменной. Оценка — функция, которая назначает каждой логической переменной любого T (для правды) или F (для ошибочности). Так, например, используя логические переменные A и B, двойные соединительные слова и представляя дизъюнкцию и соединение соответственно и одноместное соединительное отрицание представления, следующая формула может быть получена::.

Оценка здесь должна назначить на каждый из A и B или T или F. Но независимо от того как это назначение сделано, полная формула выйдет верная. Поскольку, если первое соединение не удовлетворено особой оценкой, то одному из A и B назначают F, который заставит передачу, позже разобщенную быть T.

Определение и примеры

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

Есть бесконечно много тавтологий. Примеры включают:

• («A или не»), закон исключенной середины. У этой формулы есть только одна логическая переменная, A. Любая оценка для этой формулы должна, по определению, назначить ту из ценностей правды, верных или ложных, и назначить другую стоимость правды.
• («если A подразумевает, что B тогда не-B подразумевает не-A», и наоборот), который выражает закон противопоставления.
• («если не-A подразумевает и B и его отрицание не-B, то не — Необходимость быть ложным, тогда Необходимость быть верным»), который является принципом, известным как доведение до абсурда.
• («если не и A и B, то не-A или не-B», и наоборот), который известен как закон де Моргана.
• («если A подразумевает B, и B подразумевает C, то A подразумевает C»), который является принципом, известным как силлогизм.
• (если по крайней мере один из A или B верен, и каждый подразумевает C, то C должен быть верным также), который является принципом, известным как доказательство случаями.

Минимальная тавтология — тавтология, которая не является случаем более короткой тавтологии.

• тавтология, но не минимальная, потому что это — экземпляр.

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

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

Например, рассмотрите формулу

:

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

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

Также возможно определить дедуктивную систему (система доказательства) для логической логики как более простой вариант дедуктивных систем, используемых для логики первого порядка (см. Клини 1967, Секунда 1.9 для одной такой системы). Доказательство тавтологии в соответствующей системе вычитания может быть намного короче, чем полная таблица истинности (формула с n логическими переменными требует таблицы истинности с 2 линиями, которая быстро становится неосуществимой как n увеличения). Системы доказательства также требуются для исследования intuitionistic логической логики, в которой не может использоваться метод таблиц истинности, потому что закон исключенной середины не принят.

Тавтологическое значение

Формула R, как говорят, тавтологическим образом подразумевает формулу S, если каждая оценка, которая заставляет R быть верным также, заставляет S быть верным. Эта ситуация обозначена. Это эквивалентно формуле, являющейся тавтологией (Клини 1967 p. 27).

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

Это следует из определения, которое, если формула R — противоречие тогда R тавтологическим образом, подразумевает каждую формулу, потому что нет никакой оценки правды, которая заставляет R быть верным и таким образом, определение тавтологического значения тривиально удовлетворено. Точно так же, если S — тавтология тогда S, тавтологическим образом подразумевается каждой формулой.

Замена

Есть общая процедура, правило замены, которое позволяет дополнительным тавтологиям быть

построенный из данной тавтологии (Клини 1 967 секунд. 3). Предположим, что S — тавтология и для

каждая логическая переменная в S фиксированное предложение S выбрана. Тогда

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

Например, позвольте S быть, тавтология.

Позвольте S быть и позволить S быть.

Это следует из правила замены что предложение

:

тавтология.

Эффективная проверка и Булева проблема выполнимости

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

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

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

Проблемой определения, есть ли какая-либо оценка, которая делает формулу верной, является Булева проблема выполнимости; проблема проверки тавтологий эквивалентна этой проблеме, потому что подтверждение, что предложение S является тавтологией, эквивалентно подтверждению, что нет никакого удовлетворения оценки. Известно, что Булева проблема выполнимости — полный NP, и широко полагала, что нет никакого многочленно-разового алгоритма, который может выполнить его. Текущее исследование сосредотачивается на нахождении алгоритмов, которые выступают хорошо на специальных классах формул или заканчиваются быстро в среднем даже при том, что некоторые входы могут заставить их брать намного дольше.

Тавтологии против законности в логике первого порядка

Фундаментальное определение тавтологии находится в контексте логической логики. Определение может быть расширено, однако, к предложениям в логике первого порядка (см. Enderton (2002, p. 114) и Клини (1967 secs. 17–18)). Эти предложения могут содержать кванторы, в отличие от предложений логической логики. В контексте логики первого порядка различие сохраняется между логической законностью, предложения, которые верны в каждой модели и тавтологиях, которые являются надлежащим подмножеством логической законности первого порядка. В контексте логической логики совпадают эти два условия.

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

потому что тавтология логической логики, тавтология в первой логике заказа. Точно так же на языке первого порядка с одноместным отношением символы R, S, T, следующее предложение — тавтология:

:

Это получено, заменив, с, и в логической тавтологии.

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

:

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

См. также

Нормальные формы

• Алгебраическая нормальная форма

• Соединительная нормальная форма

• Дизъюнктивая нормальная форма

• Логическая оптимизация

Связанные логические темы

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

• Булева область

• Булева функция

• Список логических символов

• Логический синтез

• Логическое следствие

• Логический граф

• Праздная правда

• Bocheński, J. M. (1959) Précis Математической Логики, переведенной с французских и немецких выпусков Отто Бирда, Дордрехта, Южной Голландии:D. Reidel.
• Enderton, H. B. (2002) А Математическое Введение в Логику, Harcourt/Academic Press, ISBN 0-12-238452-0.
• Клини, S. C. (1967) Математическая Логика, переизданный 2002, Дуврские Публикации, ISBN 0-486-42533-9.
• Райхенбах, H. (1947). Элементы Символической Логики, переизданный 1980, Дувр, ISBN 0-486-24004-5
• Витгенштейн, L. (1921). «Logisch-philosophiche Abhandlung», Annalen der Naturphilosophie (Лейпциг), v. 14, стр 185-262, переизданный в английском переводе как Tractatus logico-philosophicus, Нью-Йорк и Лондон, 1922.

Внешние ссылки

---

ru.knowledgr.com