Шпаргалка по "Логике"

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

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

Пусть элементарными высказываниями являются А, В, С. Записи

¬ A\wedge BC и (B)\wedge(B\veeA→C)

c формальной точки зрения  не являются формулами, так  как мы натыкаемся при их  разборе на нарушение правил  построения формул. (В первом случае  отсутствует логическая связка  между B и C и отсутствуют скобки вокруг ¬A. Во втором случае формула нулевого уровня В включена в скобки). А записи

(¬ A)\wedge(B\veeC) и B\wedge((B\veeA)→C)

вполне соответствуют  требованиям построения формулы. В  процессе анализа формулы (¬ A)\wedge(B\veeC) выделяются следующие её части:

               ( ¬A ) \wedge ( B\veeC )

                      \wedge                     | Связующее действие

                 ¬A       B \vee C             | Разделённые части (формулы первого уровня)

                 ¬          \vee               | Связующее действие

                 A        B    C             | Разделённые части (формулы нулевого  уровня)

                                             | Все разделённые части являются  элементарными высказываниями; разбор  закончен.

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

 

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

Если опущены внешние  скобки, то они восстанавливаются.

Если рядом стоят две  конъюнкции или дизъюнкции (например, A \wedge B \wedge C), то в скобки заключается сначала самая левая часть (т.е. две подформулы со связкой между ними). (Говорят также, что эти связки левоассоциативны.)

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

Интерпретацией (моделью) языка  логики высказываний называется функция  из множества всех пропозициональных  переменных в множество истинностных значений {0, 1}. Основной задачей логики высказываний является установление истинностного значения формулы, если даны истинностные значения входящих в неё переменных. Истинностное значение формулы в таком случае определяется индуктивно (с шагами, которые использовались при построении формулы) с использованием таблиц истинности связок

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

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

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

 

Логика высказываний

ЛОГИКА ВЫСКАЗЫВАНИЙ - раздел символической логики, изучающий  рассуждения и другие языковые контексты  без учета внутренней структуры  входящих в них простых высказываний. В связи с этим, язык Л.в. содержит нелогические символы лишь одного типа — пропозициональные переменные, которые выступают в роли параметров простых высказываний естественного языка. Логические символы в Л.в. также принадлежат одному типу. Это пропозициональные связки, образующие из менее сложных формул (предложений) более сложные.

Наиболее употребимы следующие пропозициональные связки: «¬» — отрицание («неверно, что...»), «&» («∧») — конъюнкция («и»), «v» — нестрогая дизъюнкция («или»), «v» — строгая дизъюнкция («либо... либо...»), «⇒» — импликация («если..., то...»), «⇔» — эквиваленция («если и только если»).

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

В классической Л.в. принимаются следующие условия истинности и ложности формул: формула ¬А истинна, если и только если формула А ложна; формула А&В истинна, если и только если и А, и В истинны; формула A v В истинна, если и только если по крайней мере одна из формул — А или В — истинна; формула A v В истинна, если и только если ровно одна из формул — либо А, либо В — истинна; формула А ⇒ В истинна, если и только если формула А ложна, или формула В истинна; формула А ⇔ В истинна, если и только если формулы А и В принимают одинаковые значения.

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

В силу того что множество  функций ис-тинности бесконечно, в Л .в. важен вопрос о существовании конечных наборов пропози-циональных связок (их называют функционально полными системами связок), таких, что любая функция истинности может быть выражена формулой, содержащей лишь связки из данного набора. Примерами функционально полных систем связок являются {¬ &},{¬, v}, {¬,⇒}.

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

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

Основы Л.в. были заложены уже в логике стоиков. Многие законы этой теории и формы правильных рассуждений были выделены в средневековой логике. В современном виде Л.в. была оформлена в работах Г. Фреге, Б. Рассела и А. Уайтхеда, а также Д. Гильберта и его учеников.

ВОПРОС 10

 

Алгоритм построения таблицы истинности

1.      Посчитать  количество переменных (n) в логическом  выражении.

2.      Определить  число строк в таблице, которое  равно m=2n .

3.      Посчитать  количество логических операций  и определить количество  столбцов  в таблице, которое равно: количество  переменных + количество операций.

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

5.      Заполнить  столбцы входных  переменных  наборами значений:

а) разделить колонку 1-ой переменной пополам, заполнить верхнюю  часть нулями, а нижнюю – единицами

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

в) третью разделить на 8 и  т.д.

6.   Провести заполнение  таблицы истинности по столбцам, выполняя логические операции.

ВОПРОС 11

Определение 4.1. Формулы F(X_1,X_2,\ldots,X_n) и H(X_1,X_2,\ldots,X_n) алгебры высказываний называются равносильными (эквивалентными), если при любых значениях входящих в них пропозициональных переменных логические значения получающихся из формул F и H высказываний совпадают. Для указания равносильности формул используют обозначение F\cong H. Определение равносильности формул можно записать символически для любых конкретных высказываний A_1,A_2,\ldots,A_n:

Равносильные преобразования формул

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

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

 

 

Равносильности в логике и тождества в алгебре

Можно провести параллель  между понятием логической равносильности формул в алгебре высказываний и  известным понятием тождества школьной алгебры. Равносильность формул F(X_1,\ldots,X_n) и H(X_1,\ldots,X_n) — это не что иное, как их тождественное равенство с точки зрения школьной алгебры, с той лишь разницей, что тождественность рассматривается относительно различных базисных множеств: в школьной алгебре — относительно множества \mathbb{R} всех вещественных чисел, а в алгебре логики — относительно двухэлементного множества \{0;1\}.

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

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

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

ВОПРОС 12 см в инете

Булевой алгеброй[1][2][3] называется непустое множество A с двумя бинарными  операциями \land (аналог конъюнкции), \lor (аналог дизъюнкции), унарной операцией \lnot (аналог отрицания) и двумя выделенными элементами: 0 (или Ложь) и 1 (или Истина) такими, что для всех a, b и c из множества A верны следующие аксиомы:

 

В булевых алгебрах существуют двойственные утверждения, они либо одновременно верны, либо одновременно неверны. Именно, если в формуле, которая  верна в некоторой булевой  алгебре, поменять все конъюнкции на дизъюнкции, 0 на 1, ≤ на ≥ и наоборот, то получится формула, также истинная в этой булевой алгебре. Это следует из симметричности аксиом относительно таких замен.

Представления булевых алгебр

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

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

 

Вопрос 13

 

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