Логика высказываний
<imagemap>: неверное или отсутствующее изображение |
Для улучшения этой статьи желательно?:
|
Логика высказываний, или пропозициональная логика (лат. propositio — «высказывание»[1]), или исчисление высказываний[2] — это раздел символической логики, изучающий сложные высказывания, образованные из простых, и их взаимоотношения. В отличие от логики предикатов, внутренняя структура простых высказываний не рассматривается, а учитывается лишь, с помощью каких союзов и в каком порядке простые высказывания сочленяются в сложные[3].
Несмотря на свою важность и широкую сферу применения, логика высказываний является простейшей логикой и имеет очень ограниченные средства для исследования суждений[2].
Содержание
Язык логики высказываний
Язык логики высказываний (пропозициональный язык[4]) — искусственный язык, предназначенный для анализа логической структуры сложных высказываний[1].
Алфавит языка логики высказываний
Исходные символы, или алфавит языка логики высказываний, разделены на следующие три категории[1][5]:
- пропозициональные буквы (пропозициональные переменные):
- <math>p, q, r, s, t, p_1, q_1, r_1, s_1, t_1, ...</math>
- логические знаки (логические союзы):
| Символ | Значение |
|---|---|
| <math>\neg</math> | Знак отрицания |
| <math>\land</math> | Знак конъюнкции («И») |
| <math>\vee</math> | Знак дизъюнкции («включающее ИЛИ») |
| <math>\dot\or</math> | Знак строгой дизъюнкции («исключающее ИЛИ») |
| <math>\rightarrow</math> | Знак импликации |
| <math>\leftrightarrow</math> | Знак эквивалентности |
- технические знаки:
| Символ | Значение |
|---|---|
| <math>(</math> | Левая скобка |
| <math>)</math> | Правая скобка |
Других знаков в алфавите языка логики высказываний нет.
Пропозициональные переменные
Пропозициональная переменная — переменная, которая в пропозициональных формулах служит для замены собой элементарных логических высказываний[3].
Пропозициональные формулы
Роль структурных образований, аналогичных элементарным и сложным высказываниям, играют в этом языке формулы. Пропозициональная формула — конечная последовательность знаков алфавита, построенная по изложенным ниже правилам и образующая законченное выражение языка логики высказываний[1]. Заглавные латинские буквы <math>A</math>, <math>B</math> и другие, которые употребляются в определении формулы, принадлежат не языку логики высказываний, а его метаязыку, то есть языку, который используется для описания самого языка логики высказываний. Содержащие метабуквы выражения <math>\neg A</math>, <math>(A \to B)</math> и другие — не пропозициональные формулы, а схемы формул. Например, выражение <math>(A \wedge B)</math> есть схема, под которую подходят формулы <math>(p \wedge q)</math>, <math>(p \wedge (r \vee s))</math> и другие[1].
Индуктивное определение формулы логики высказываний:[4][1]
- пропозициональная переменная есть формула;
- если <math>A</math> — произвольная формула, то <math>\neg A</math> — тоже формула;
- если <math>A</math> и <math>B</math> — произвольные формулы, то <math>(A \to B)</math>, <math>(A \wedge B)</math>, <math>(A \leftrightarrow B)</math>, <math>(A \vee B)</math> и <math>(A ~ \dot\or ~ B ~)</math> — тоже формулы.
Других формул в языке логики высказываний нет.
Относительно любой последовательности знаков алфавита языка логики высказываний можно решить, является она формулой или нет. Если эта последовательность может быть построена в соответствии с пп. 1—3 определения формулы, то она формула, если нет, то не формула[1].
Язык логики высказываний можно рассматривать как множество пропозициональных формул[4].
Для формул логики высказываний можно определить понятие интерпретации, как приписывание каждой пропозициональной переменной истинностного значения[6] («истина» или «ложь», хотя исчисление высказываний никак не ограничивает множество возможных значений при интерпретации: например, можно задать интерпретацию как отображение в множество <math>\{0,1,\ldots,k\}</math>, где <math>k \in \mathbb{N}</math>, — такой подход может использоваться, к примеру, при доказательстве независимости схем аксиом исчисления высказываний).
Соглашения о скобках
Поскольку в построенных по определению формулах оказывается слишком много скобок, иногда и не обязательных для однозначного понимания формулы, математики приняли соглашения о скобках, по которым некоторые из скобок можно опускать. Записи с опущенными скобками восстанавливаются по следующим правилам.
- Если опущены внешние скобки, то они восстанавливаются.
- Если рядом стоят две конъюнкции или дизъюнкции (например, <math>A \wedge B \wedge C</math>), то в скобки заключается сначала самая левая часть (то есть две подформулы со связкой между ними). (Говорят также, что эти связки левоассоциативны.)
- Если рядом стоят разные связки, то скобки расставляются согласно приоритетам: <math>\neg, \wedge, \vee</math> и <math>\to</math> (от высшего к низшему).
Когда говорят о длине формулы, имеют в виду длину подразумеваемой (восстанавливаемой) формулы, а не сокращённой записи.
Например: запись <math>A \vee B \wedge \neg C</math> означает формулу <math>(A \vee (B \wedge ( \neg C)))</math>, а её длина равна 12.
Интерпретация языка логики высказываний
Основной задачей логики высказываний является установление истинностного значения формулы, если даны истинностные значения входящих в неё переменных. Истинностное значение формулы в таком случае определяется индуктивно (с шагами, которые использовались при построении формулы) с использованием таблиц истинности связок[7].
Пусть <math>\mathbb{B}</math> — множество всех истинностных значений <math>\{0, 1\}</math>, а <math>Vars</math> — множество пропозициональных переменных. Тогда интерпретацию (или модель) языка логики высказываний можно представить в виде отображения
- <math>M\colon Vars \to \mathbb{B}</math>,
которое каждой пропозициональной переменной <math>p</math> сопоставляет истинностное значение <math>M(p)</math>[7].
Оценка отрицания <math>\neg p</math> задаётся таблицей:
| <math>p</math> | <math>\neg p</math> |
|---|---|
Значения двухместных логических связок <math>\rightarrow</math> (импликация), <math>\vee</math> (дизъюнкция) и <math>\wedge</math> (конъюнкция) определяются так:
| <math>p</math> | <math>q</math> | <math>p\rightarrow q</math> | <math>p \wedge q</math> | <math>p \vee q</math> |
|---|---|---|---|---|
Тождественно истинные формулы (тавтологии)
Формула является тождественно истинной, если она истинна при любых значениях входящих в неё переменных (то есть, при любой интерпретации)[8]. Далее перечислены несколько широко известных примеров тождественно истинных формул логики высказываний:
- <math> \neg (p \vee q) \leftrightarrow (\neg p \wedge \neg q)</math>;
- <math> \neg (p \wedge q) \leftrightarrow (\neg p \vee \neg q)</math>;
- <math>(p\rightarrow q)\leftrightarrow(\neg q\rightarrow \neg p)</math>;
- законы поглощения:
- <math>p\vee(p\wedge q)\leftrightarrow p</math>;
- <math>p\wedge(p\vee q)\leftrightarrow p</math>;
- <math>p\wedge(q\vee r)\leftrightarrow(p\wedge q)\vee(p \wedge r)</math>;
- <math>p\vee(q\wedge r)\leftrightarrow(p\vee q)\wedge(p \vee r)</math>.
Исчисление высказываний
Одним из возможных вариантов (Гильбертовской) аксиоматизации логики высказываний является следующая система аксиом:
<math>A_1 : A \rightarrow (B \rightarrow A)</math>;
<math>A_2 : (A \rightarrow (B \rightarrow C)) \rightarrow ((A \rightarrow B) \rightarrow (A \rightarrow C))</math>;
<math>A_3 : A \wedge B \rightarrow A</math>;
<math>A_4 : A \wedge B \rightarrow B</math>;
<math>A_5 : A \rightarrow (B \rightarrow (A \wedge B))</math>;
<math>A_6 : A \rightarrow (A \vee B)</math>;
<math>A_7 : B \rightarrow (A \vee B)</math>;
<math>A_8 : (A \rightarrow C) \rightarrow ((B \rightarrow C) \rightarrow ((A \vee B) \rightarrow C))</math>;
<math>A_9 : \neg A \rightarrow (A \rightarrow B)</math>;
<math>A_{10} : (A \rightarrow B) \rightarrow ((A \rightarrow \neg B)\rightarrow \neg A)</math>;
<math>A_{11} : A\vee\neg A</math>.
вместе с единственным правилом:
<math>\frac{A \quad (A \rightarrow B)}{B}</math> (Modus ponens)
Теорема корректности исчисления высказываний утверждает, что все перечисленные выше аксиомы являются тавтологиями, а с помощью правила modus ponens из истинных высказываний можно получить только истинные. Доказательство этой теоремы тривиально и сводится к непосредственной проверке. Куда более интересен тот факт, что все остальные тавтологии можно получить из аксиом с помощью правила вывода — это так называемая теорема полноты логики высказываний.
См. также
Напишите отзыв о статье "Логика высказываний"
Примечания
- ↑ 1 2 3 4 5 6 7 Чупахин, Бродский, 1977, с. 203—205.
- ↑ 1 2 Кондаков, 1971, статья «Исчисление высказываний».
- ↑ 1 2 НФЭ, 2010.
- ↑ 1 2 3 Герасимов, 2011, с. 13.
- ↑ Войшвилло, Дегтярев, 2001, с. 91—94.
- ↑ Чень Ч., Ли Р. Математическая логика и автоматическое доказательство теорем. — С. 18-19
- ↑ 1 2 Герасимов, 2011, с. 17—19.
- ↑ Герасимов, 2011, с. 19.
Литература
- Кондаков Н. И. Логический словарь / Горский Д. П.. — М.: Наука, 1971. — 656 с.
- Чупахин И. Я.,Бродский И. Н. Формальная логика. — Ленинград: Издательство Ленинградского университета, 1977. — 357 с.
- Войшвилло Е. К., Дегтярев М. Г. Логика. — М.: ВЛАДОС-ПРЕСС, 2001. — 528 с. — ISBN 5-305-00001-7.
- Игошин В. И. Математическая логика и теория алгоритмов. — 2-е изд., стереотип.. — М.: Издательский центр «Академия», 2008. — 448 с. — ISBN 978-5-7695-4593-1.
- Логика высказываний // Новая философская энциклопедия. — М., 2010. — Т. 2. — С. 415—418.
- Герасимов А. С. [gas-teach.narod.ru/cmlct/CMLCT_3ed.pdf Курс математической логики и теории вычислимости]. — СПб.: Издательство «ЛЕМА», 2011. — 284 с. — ISBN 978-5-98709-292-7.
Отрывок, характеризующий Логика высказываний
Дядюшка ни на кого не глядя сдунул пыль, костлявыми пальцами стукнул по крышке гитары, настроил и поправился на кресле. Он взял (несколько театральным жестом, отставив локоть левой руки) гитару повыше шейки и подмигнув Анисье Федоровне, начал не Барыню, а взял один звучный, чистый аккорд, и мерно, спокойно, но твердо начал весьма тихим темпом отделывать известную песню: По у ли и ице мостовой. В раз, в такт с тем степенным весельем (тем самым, которым дышало всё существо Анисьи Федоровны), запел в душе у Николая и Наташи мотив песни. Анисья Федоровна закраснелась и закрывшись платочком, смеясь вышла из комнаты. Дядюшка продолжал чисто, старательно и энергически твердо отделывать песню, изменившимся вдохновенным взглядом глядя на то место, с которого ушла Анисья Федоровна. Чуть чуть что то смеялось в его лице с одной стороны под седым усом, особенно смеялось тогда, когда дальше расходилась песня, ускорялся такт и в местах переборов отрывалось что то.– Прелесть, прелесть, дядюшка; еще, еще, – закричала Наташа, как только он кончил. Она, вскочивши с места, обняла дядюшку и поцеловала его. – Николенька, Николенька! – говорила она, оглядываясь на брата и как бы спрашивая его: что же это такое?
Николаю тоже очень нравилась игра дядюшки. Дядюшка второй раз заиграл песню. Улыбающееся лицо Анисьи Федоровны явилось опять в дверях и из за ней еще другие лица… «За холодной ключевой, кричит: девица постой!» играл дядюшка, сделал опять ловкий перебор, оторвал и шевельнул плечами.
– Ну, ну, голубчик, дядюшка, – таким умоляющим голосом застонала Наташа, как будто жизнь ее зависела от этого. Дядюшка встал и как будто в нем было два человека, – один из них серьезно улыбнулся над весельчаком, а весельчак сделал наивную и аккуратную выходку перед пляской.
– Ну, племянница! – крикнул дядюшка взмахнув к Наташе рукой, оторвавшей аккорд.
Наташа сбросила с себя платок, который был накинут на ней, забежала вперед дядюшки и, подперши руки в боки, сделала движение плечами и стала.
Где, как, когда всосала в себя из того русского воздуха, которым она дышала – эта графинечка, воспитанная эмигранткой француженкой, этот дух, откуда взяла она эти приемы, которые pas de chale давно бы должны были вытеснить? Но дух и приемы эти были те самые, неподражаемые, не изучаемые, русские, которых и ждал от нее дядюшка. Как только она стала, улыбнулась торжественно, гордо и хитро весело, первый страх, который охватил было Николая и всех присутствующих, страх, что она не то сделает, прошел и они уже любовались ею.
Она сделала то самое и так точно, так вполне точно это сделала, что Анисья Федоровна, которая тотчас подала ей необходимый для ее дела платок, сквозь смех прослезилась, глядя на эту тоненькую, грациозную, такую чужую ей, в шелку и в бархате воспитанную графиню, которая умела понять всё то, что было и в Анисье, и в отце Анисьи, и в тетке, и в матери, и во всяком русском человеке.
– Ну, графинечка – чистое дело марш, – радостно смеясь, сказал дядюшка, окончив пляску. – Ай да племянница! Вот только бы муженька тебе молодца выбрать, – чистое дело марш!
– Уж выбран, – сказал улыбаясь Николай.
– О? – сказал удивленно дядюшка, глядя вопросительно на Наташу. Наташа с счастливой улыбкой утвердительно кивнула головой.
– Еще какой! – сказала она. Но как только она сказала это, другой, новый строй мыслей и чувств поднялся в ней. Что значила улыбка Николая, когда он сказал: «уж выбран»? Рад он этому или не рад? Он как будто думает, что мой Болконский не одобрил бы, не понял бы этой нашей радости. Нет, он бы всё понял. Где он теперь? подумала Наташа и лицо ее вдруг стало серьезно. Но это продолжалось только одну секунду. – Не думать, не сметь думать об этом, сказала она себе и улыбаясь, подсела опять к дядюшке, прося его сыграть еще что нибудь.
Дядюшка сыграл еще песню и вальс; потом, помолчав, прокашлялся и запел свою любимую охотническую песню.
Как со вечера пороша
Выпадала хороша…
Дядюшка пел так, как поет народ, с тем полным и наивным убеждением, что в песне все значение заключается только в словах, что напев сам собой приходит и что отдельного напева не бывает, а что напев – так только, для складу. От этого то этот бессознательный напев, как бывает напев птицы, и у дядюшки был необыкновенно хорош. Наташа была в восторге от пения дядюшки. Она решила, что не будет больше учиться на арфе, а будет играть только на гитаре. Она попросила у дядюшки гитару и тотчас же подобрала аккорды к песне.
В десятом часу за Наташей и Петей приехали линейка, дрожки и трое верховых, посланных отыскивать их. Граф и графиня не знали где они и крепко беспокоились, как сказал посланный.
Петю снесли и положили как мертвое тело в линейку; Наташа с Николаем сели в дрожки. Дядюшка укутывал Наташу и прощался с ней с совершенно новой нежностью. Он пешком проводил их до моста, который надо было объехать в брод, и велел с фонарями ехать вперед охотникам.
– Прощай, племянница дорогая, – крикнул из темноты его голос, не тот, который знала прежде Наташа, а тот, который пел: «Как со вечера пороша».
В деревне, которую проезжали, были красные огоньки и весело пахло дымом.
– Что за прелесть этот дядюшка! – сказала Наташа, когда они выехали на большую дорогу.
– Да, – сказал Николай. – Тебе не холодно?
– Нет, мне отлично, отлично. Мне так хорошо, – с недоумением даже cказала Наташа. Они долго молчали.
Ночь была темная и сырая. Лошади не видны были; только слышно было, как они шлепали по невидной грязи.
Что делалось в этой детской, восприимчивой душе, так жадно ловившей и усвоивавшей все разнообразнейшие впечатления жизни? Как это всё укладывалось в ней? Но она была очень счастлива. Уже подъезжая к дому, она вдруг запела мотив песни: «Как со вечера пороша», мотив, который она ловила всю дорогу и наконец поймала.
– Поймала? – сказал Николай.
– Ты об чем думал теперь, Николенька? – спросила Наташа. – Они любили это спрашивать друг у друга.
– Я? – сказал Николай вспоминая; – вот видишь ли, сначала я думал, что Ругай, красный кобель, похож на дядюшку и что ежели бы он был человек, то он дядюшку всё бы еще держал у себя, ежели не за скачку, так за лады, всё бы держал. Как он ладен, дядюшка! Не правда ли? – Ну а ты?
– Я? Постой, постой. Да, я думала сначала, что вот мы едем и думаем, что мы едем домой, а мы Бог знает куда едем в этой темноте и вдруг приедем и увидим, что мы не в Отрадном, а в волшебном царстве. А потом еще я думала… Нет, ничего больше.
– Знаю, верно про него думала, – сказал Николай улыбаясь, как узнала Наташа по звуку его голоса.
– Нет, – отвечала Наташа, хотя действительно она вместе с тем думала и про князя Андрея, и про то, как бы ему понравился дядюшка. – А еще я всё повторяю, всю дорогу повторяю: как Анисьюшка хорошо выступала, хорошо… – сказала Наташа. И Николай услыхал ее звонкий, беспричинный, счастливый смех.
– А знаешь, – вдруг сказала она, – я знаю, что никогда уже я не буду так счастлива, спокойна, как теперь.
– Вот вздор, глупости, вранье – сказал Николай и подумал: «Что за прелесть эта моя Наташа! Такого другого друга у меня нет и не будет. Зачем ей выходить замуж, всё бы с ней ездили!»
«Экая прелесть этот Николай!» думала Наташа. – А! еще огонь в гостиной, – сказала она, указывая на окна дома, красиво блестевшие в мокрой, бархатной темноте ночи.
Граф Илья Андреич вышел из предводителей, потому что эта должность была сопряжена с слишком большими расходами. Но дела его всё не поправлялись. Часто Наташа и Николай видели тайные, беспокойные переговоры родителей и слышали толки о продаже богатого, родового Ростовского дома и подмосковной. Без предводительства не нужно было иметь такого большого приема, и отрадненская жизнь велась тише, чем в прежние годы; но огромный дом и флигеля всё таки были полны народом, за стол всё так же садилось больше человек. Всё это были свои, обжившиеся в доме люди, почти члены семейства или такие, которые, казалось, необходимо должны были жить в доме графа. Таковы были Диммлер – музыкант с женой, Иогель – танцовальный учитель с семейством, старушка барышня Белова, жившая в доме, и еще многие другие: учителя Пети, бывшая гувернантка барышень и просто люди, которым лучше или выгоднее было жить у графа, чем дома. Не было такого большого приезда как прежде, но ход жизни велся тот же, без которого не могли граф с графиней представить себе жизни. Та же была, еще увеличенная Николаем, охота, те же 50 лошадей и 15 кучеров на конюшне, те же дорогие подарки в именины, и торжественные на весь уезд обеды; те же графские висты и бостоны, за которыми он, распуская всем на вид карты, давал себя каждый день на сотни обыгрывать соседям, смотревшим на право составлять партию графа Ильи Андреича, как на самую выгодную аренду.
Граф, как в огромных тенетах, ходил в своих делах, стараясь не верить тому, что он запутался и с каждым шагом всё более и более запутываясь и чувствуя себя не в силах ни разорвать сети, опутавшие его, ни осторожно, терпеливо приняться распутывать их. Графиня любящим сердцем чувствовала, что дети ее разоряются, что граф не виноват, что он не может быть не таким, каким он есть, что он сам страдает (хотя и скрывает это) от сознания своего и детского разорения, и искала средств помочь делу. С ее женской точки зрения представлялось только одно средство – женитьба Николая на богатой невесте. Она чувствовала, что это была последняя надежда, и что если Николай откажется от партии, которую она нашла ему, надо будет навсегда проститься с возможностью поправить дела. Партия эта была Жюли Карагина, дочь прекрасных, добродетельных матери и отца, с детства известная Ростовым, и теперь богатая невеста по случаю смерти последнего из ее братьев.
