Методические рекомендации по изучению дисциплины (стр. 3 )

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

А	В	(А&В)	(АÚВ)	(А→В)	(А↔В)	┐А
л	л	л	л	и	и	и
л	и	л	и	и	л	и
и	л	л	и	л	л	л
и	и	и	и	и	и	л

Таблица 2.1.2

Истинностные значения, данные в таблице для высказываний (А&В); (АÚВ); (А→В); (А↔В); ┐А, в основном согласуются с интуитивными представлениями, основанными на практике человеческого мышления. Некоторое недоумение может, вероятно, вызвать лишь принятое соглашение считать истинностным значением высказывания (А→В) при А=л; В=и, значение и. Тем не менее, целесообразность именно такого определения импликации при А=л; В=и может быть объяснена следующим образом. Рассуждения, проводимые по схеме: «Если А, то В.» обычно употребляются в том случае, когда неизвестно истинно ли А на самом деле или нет. Так, следователь, отрабатывая версию возможного хода событий, которые привели к преступлению, с логической точки зрения действует безупречно, хотя посылка, положенная в основу версии, в действительности, может оказаться ложной. Аналогично, говоря, например, что если завтра будет солнечный день, то мы пойдем на реку загорать, мы утверждает только то, что какое-то событие произойдет (поход на реку) при выполнении некоторого условия (отсутствие дождя). И то, что событие на самом деле не произошло (поход на реку не состоялся), не означает, что высказывание «Если завтра будет солнечный день, то мы пойдем на реку загорать.» ложно, так как в нем ничего не заявлено о походе на реку, в случае невыполнения данного условия.

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

а) «Если х0 – корень уравнения , то х0 является корнем уравнения .»;

б) «Если натуральное число п0 делится на 10, то оно делится и на 5.».

Мы «автоматически» признаем эти утверждения истинными, хотя уравнение может не иметь корней, а число п0 – не делиться на 10.

Пусть в качестве исходных высказываний взяты высказывания А1; А2; …; Ап; … . Процедуру образования сложных высказываний, исходя из высказываний А1; А2; …; Ап; … можно описать, как конструкцию пошагового характера, подобно тому, как это было сделано в пункте 1.3 (смотри пример 1.3.5) при построении класса множеств Т. Высказывания, полученные на шаге п (п=1, 2, …) будем называть высказываниями этого шага.

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

A; B; C; D; …; A1; A2;…; An;…; B1; B2;…;Bn;… .

Чтобы показать из каких исходных высказываний построено данное высказывание А, они вписываются в скобках (через запятую) справа от буквы А: А(А1;А2;…;Ап), что отражает функциональную зависимость А от А1;А2;…;Ап. Отметим, что, в общем случае, запись А(А1;А2;…;Ап) будет означать, что исходные высказывания которые явно входят в формулу А(А1;А2;…;Ап) находятся среди А1;А2;…;Ап.

Шаг 0 Все исходные высказывания

А1; А2; …; Ап; …;

объявляются высказываниями шага 0.

Предполагая, что все высказывания шагов 0; 1; …; t уже определены и А1 и А2 – любые два высказывания, построенные на одном из этих шагов, переходим к следующему шагу.

Шаг (t+1) Высказывания, полученные из А1 и А2, не более чем однократным, применением к ним операций , т. е. высказывания А1; А2; ; ; ; ; , объявляются высказываниями шага (t+1).

В частности, высказывания А4; (А3&А7); ┐А2; (А5→А1); (А6&А3); (А1ÚА2); (А10↔А8); ┐А5 и т. п. будут получены на первом шаге. Высказывания А2; ┐А5; (А10↔А10); (А4& (А3ÚА7)); (А2↔┐А5); ((А3&А10)Ú (А6→А4)) и т. п. будут получены на втором шаге и т. д.

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

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

Нетрудно видеть, что если высказывание А=А(А1;А2;…;Ап) является высказыванием шага t, то оно является высказыванием каждого последующего шага: t+1; t+2; … . Номер шага, на котором это высказывание появляется впервые, будем называть сложностью высказывания А. Сложность высказывания А будем обозначать через S(А).

Специфику определения логических операций отражают диаграммы Эйлера-Венна. На этих диаграммах исходные высказывания А и В, входящие в сложные высказывания

(А&В); (АÚВ); (А→В); (А↔В);

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

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

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

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

Пример Построим диаграмму Эйлера-Венна для высказывания .

Шаг 1

Шаг 2

.

Рисунок 2.1.2

 

Следуя пошаговому процессу построения высказывания А, начиная с шага 1, построим диаграмму для этого высказывания (смотри рисунок 2.1.2).

Формулы алгебры высказываний

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

а) Символы исходных высказываний: А1;А2;…;Ап; … .

б) Символы логических операций: &; Ú; →; ↔; ┐.

в) Символы (, ) – левой и правой скобок и символ ; - точки с запятой.

В соответствии с этим, любое высказывание А=А(А1;А2;…;Ап) можно рассматривать с двух точек зрения: формальной и содержательной.

1 В формальной отношении высказывание А представляет интерес, как некоторое слово в алфавите А, построенное по определенным правилам.

2 В содержательном плане высказывание А=А(А1;А2;…;Ап) интересует нас, как истинностная функция своих аргументов А1;А2;…;Ап.

Слова алфавита A, являющиеся высказываниями, будем называть формулами. Множество всех формул алфавита A обозначим через L(A) и будем называть языком алгебры высказываний.

Акцентируя внимание на первой из вышеприведенных точек зрения, мы приходим к изучению синтаксиса языка L(A) этой алгебры. Пошаговый процесс построения высказывания А показывает, что если S(A)≥1, то для высказывания А имеет место одна из следующих возможностей:

А=(В&С); А=(ВÚС); А=(В→С); А=(В↔С); А=┐В,

для некоторых высказываний В и С таких, что S(B)<S(A) и S(С)<S(A). Формулы В и С естественно назвать подформулами формулы А. Отметим, что формулами В и С не исчерпывается совокупность всех подформул формулы А, т. к. В и С, в свою очередь, могут иметь свои подформулы. В соответствии с общим пониманием части объекта, к числу подформул формулы А должна быть отнесена и сама формула А.

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

Определение а) Базис индукции (S(A) = 0) В этом случае А=Аi для некоторого , т. е. А – исходное высказывание. Все исходные высказывания являются формулами. Эти формулы называются элементарными или атомными. Подформулой любой элементарной формулы Аi является только она сама.

б) Индукционное предположение (S(А) £ t) Пусть формулы, сложности ≤ t u все подформулы любой формулы АÎL(A), сложность которой по превосходит t, уже определены и В, С – формулы из L(A),сложности £ t.

в) Индукционный шаг (S(A) = t + 1) Сложные высказывания

(В&С); (ВÚС); (В→С); (В↔С); ┐В

являются формулами. Так как S(В) £ t и S(С) £ t, то все подформулы формул В и С (согласно индукционного предположения) уже определены. Подформулами формулы (В f С), fÎ{&, Ú, →, ↔}; являются все подформулы формул В и С и сама эта формула. Подформулами формулы ┐В являются все подформулы формулы В и сама формула ┐В.

Из определения следует, что если А – формула и S(A)>1, то для получения формулы А нужно сначала построить все ее подформулы, сложность которых строго меньше S(A). И только после этого, на очередном шаге, нам удастся построить формулу А. Это дает возможность по любому слову алфавита А за конечное число шагов выяснить является это слово формулой или нет (т. е. понятие формулы является эффективным).

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

Процесс воссоздания будет состоять из выписывания подформул В слова А сложностей 0, 1, 2 и т. д. до тех пор пока это представляется возможным. Пусть t – наибольшая из сложностей выписанных подформул и слово А не имеет подформул сложности t+1. Слово А является формулой тогда и только тогда, когда среди выписанных подформул этого слова имеется только одна подформула В сложности t и А=В.

Пример Выясним, являются ли данные слова формулами:

а) ;

б)

а) Элементарными подформулами слова А(А1;А2;А3) являются А1; А2; А3.

Пошаговый процесс воссоздания слова А(А1;А2;А3) из А1; А2; А3 выглядит следующим образом:

Шаг 0 А1; А2; А3 – подформулы сложности 0, в соответствии с пунктом а) определения 2.2.1;

Шаг 1 А3; (А1&А2) – подформулы сложности 1, в соответствии с пунктом б) определения 2.2.1;

Шаг 2 (А2&А3); (А1&А2) – подформулы сложности 2, в соответствии с пунктом б) определения 2.2.1;

Шаг 3 (А1→(А2&А3)); ((А1&А2)ÚА3) – подформулы сложности 3, в соответствии с пунктом б) определения 1.2.1;

Шаг 4 (А3«((А1&А2)ÚА3)) – подформула сложности 4, в соответствии с пунктом б) определения 2.2.1;

Шаг 5 ((А1→(А2&А3))Ú(А3«((А1&А2)ÚА3))) – подформула сложности 5, в соответствии с пунктом б) определения 2.2.1.

Наибольшая из сложностей выписанных подформул равна 5, подформула сложности 5 единственна и совпадает с А(А1;А2;А3), т. е. процесс воссоздания слова А(А1;А2;А3) удалось довести до конца и, следовательно, это слово является формулой.

б) Приведем только список подформул данного слова.

Шаг 0 А1; А2; А3;

Шаг 1 А3; (А1→А2); (А2↔А3);

Шаг 2 (А1→А2); (А2Ú А3); (А2↔А3);

Шаг 3 ((А1→А2)&А3).

На этом процесс воссоздания слова В(А1;А2;А3) обрывается. Подформула ((А1→А2)&А3) является подформулой наибольшей сложности, но она не совпадает с В(А1;А2;А3) (хотя она и единственна). Таким образом, данное слово формулой не является. Довести до конца процесс воссоздания слова В(А1;А2;А3) не удалось в связи с тем, что на следующем шаге 4 можно получить и формулу (((А1→А2)&А3)↔(А2ÚА3)) и формулу ((А2ÚА3)&(А2↔А3)), но ни одна из них не является подформулой слова В(А1;А2;А3).

В связи с этим примером отметим, что именно обязательность расстановки скобок при построении формулы (смотри пункт б) определения 2.2.1) и позволяет однозначно выделить все ее подформулы.

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

Пусть А=А(А1;А2;…;Ап) произвольная формула. Упорядоченный набор будем называть набором значений истинности (длины п) для переменных А1;А2;…;Ап соответственно. Вычисление истинностных значений формулы А на конкретных наборах значений истинности для ее переменных осуществляется индукцией по сложности этой формулы.

Истинностное значение формулы А=А(А1;А2;…;Ап) на наборе будем обозначать через .

Определение а) базис индукции (S(A)=0). Т. е. формула А имеет вид А=Аi (iÎ{1,…,n}). В этом случае полагаем .

б) индукционное предположение (S(В)≤t). Предположим, что истинностное значение любой формулы В, сложность которой не превосходит t, на наборе уже определено.

в) индукционный шаг (S(A)=t+1). В этом случае, согласно определения 2.2.1, для формулы А может иметь место одна из следующих возможностей:

в.1) А(А1;А2;…;Ап)=(В(А1;А2;…;Ап)&С(А1;А2;…;Ап));

в.2) А(А1;А2;…;Ап)=(В(А1;А2;…;Ап)ÚС(А1;А2;…;Ап));

в.3) А(А1;А2;…;Ап)=(В(А1;А2;…;Ап)→С(А1;А2;…;Ап));

в.4) А(А1;А2;…;Ап)=(В(А1;А2;…;Ап)↔С(А1;А2;…;Ап));

в.5) А(А1;А2;…;Ап)=В(А1;А2;…;Ап).

Так как S(A)=t+1, то S(В)≤t и S(С)≤t, т. е., по индукционному предположению, истинностные значения и уже определены. Тогда значение в каждом из случаев в.1) – в.5) определяется исходя из таблицы истинности (таблица 2.1.2).

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

Пример Вычислим истинностное значение формулы

на наборе . Выпишем все подформулы В этой формулы, начиная с подформул сложности 0.

S(В)=0: А1; А2; А3 ;