Человеческое мышление


Похожие статьи:

Популярные записи


  • Алгебра высказываний

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

    Простое Элементарное Высказывание Высказывание - это простое утверждение, то есть повествовательное предложение, относительно содержания которого уместно ставить вопрос о его правильности или неправильности.

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

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

    Приведем несколько примеров элементарных высказываний :

    1 Киев - столица Украины.

    2 Число 7 является простым.

    3 Число 10 больше от числа 3.

    4 Все натуральные числа являются простыми.

    5 Множество всех простых чисел является конечным.

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

    В то же время предложение "Пусть живет математическая логика"! или "Внимательно прочитайте весь этот раздел" не являются высказываниями.

    Рассматривая высказывание, виходитимо из двух основных предположений:

    1 каждое высказывание есть или истинным, или ошибочным Закон исключения третьего;

    2 ни одно высказывание не есть одновременно истинным и ошибочным Закон исключения противоречия.

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

    Будем помечать элементарные высказывания малыми латинскими буквами: A, B, C,.. возможно, с индексами, а значение высказываний "Iстинно" и "Ошибочно" - соответственно символами 1 и 0 или I и Х.

    Кроме того, будем рассматривать так называемые Переменные высказывания, какие будем помечать латинскими буквами X, Y, Z,.. возможно, с индексами и будем называть также Пропозицийними переменными. После подстановки вместо пропозицийної переменной определенного элементарного высказывания эта переменная приобретет соответствующее значение: 0 или 1.

    Сигнатура алгебры высказываний традиционно состоит из таких операции: Отрицание, Конъюнкция, Дизъюнкция но Импликация.

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

    Таблица 1

    Название

    Обозначение

    Конъюнкция

    Логическое умножение

    Логическое "И"

    Дизъюнкция

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

    Логическое "ИЛИ"

    Отрицание

    Логическое "НИ"

    -

    Импликация

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

    Будем использовать первые из приведенных названий и обозначений. Ниже подана таблица 2, что содержит определение этих операций.

    Таблица 2

    0

    1

    0

    0

    1

    1

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

    Алфавит наиболее распространенного формального языка алгебры высказываний состоит из трех групп символов :

    1 символы элементарных высказываний и пропозицийних переменных : A, B, C,.. и X, Y, Z,.. возможно с индексами;

    2 символа операций :, ;

    3 вспомогательных символа - круглые скобки : и .

    Из пропозицийних переменных и элементарных высказываний с помощью операций и скобок строятся пропозицийни формулы или просто Формулы алгебры высказываний по таким индуктивным правилам:

    1 все пропозицийни переменные и элементарные высказывания являются формулами;

    2 если A и B - формулы, то выражения A B, A B, A, A B также являются формулами;

    3 других формул, чем построенные по правилам 1 и 2, нет.

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

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

    Пусть P1, P2.., Pn - это все пропозицийни переменные, которые входят в формулу A; будем помечать этот факт A P1, P2.., Pn. Формуле A P1, P2.., Pn поставим в соответствие функцию F P1, P2.., Pn, что отмеченная на множестве Bn B={0,1} и принимает значение во множестве B, то есть функцию типа Bn B. Значение функции F на наборе значений A1, A2.., An ее переменных P1, P2.., Pn равняется значению формулы A P1, P2.., Pn при подстановке у нее вместо пропозицийних переменных P1, P2.., Pn значений A1, A2.., An соответственно.

    Заметим, что количество элементов в области определения функции F равняется 2 N, то есть |Pr1 F|=2 N.

    Функцию F называют Функцией истинности для формулы A или соответствующего составленного высказывания. Для функции истинности может быть построена так называемая Таблица истинности этой функции см. таблицу 3.

    Таблица 3

    P1 P2 ..... Pn- 1 Pn

    F P1, P2.., Pn- 1, Pn

    0 0 .. 0 0

    0 0 .. 0 1

    0 0 .. 1 0

    0 0 .. 1 1

    ........................

    1 1 .. 1 0

    1 1 .. 1 1

    f0,0,..0,0

    f0,0,..0,1

    f0,0,..1,0

    f0,0,..1,1

    ....................

    f1,1,..1,0

    f1,1,..1,1

    Среди формул алгебры высказываний особенное место занимают те формулы A P1, P2.., Pn, какие на всех наборах A1, A2.., An значения своих переменных приобретают значения 1.

    Формула алгебры высказываний A P1, P2.., Pn называется Тавтологией тогда и только затем, когда ей отвечает функция истинности, которая тождественно равняется 1.

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

    Приведем примеры некоторой важной тавтологии :

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

    P P Закон исключения противоречия,

    P P Закон тождественности.

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

    Формула алгебры высказываний A P1, P2.., Pn, какая приобретает значение 0 на всех наборах A1, A2.., An значений своих пропозицийних переменных, называется Противоречием, или Тождественно ошибочной формулой.

    Формулу, которая не является ни тавтологией, ни противоречием, называют Нейтральной.

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

    Формула, которая не является противоречием, называется Выполняемой.

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

    1. Отрицание тавтологии является противоречием и наоборот.

    2. Каждая тавтология является выполняемой формулой наоборот, вообще говоря, нет.

    3. Каждая нейтральная формула является выполняемой, но не наоборот.

    4. Отрицание выполняемой формулы может быть, как выполняемой формулой, так и невыполняемой формулой.

    Две формулы A и B алгебры высказываний называются Равносильными, если им отвечает та же функция истинности. Ривносильнисть формул A и B помечают с помощью знака = или ": записывают A= B A B Или A" B.

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

    Приведем примеры пар равносильных формул :

    A B= A B, A B= A B, A B= A B,

    A B C= A B A C, A B C= A B A C

    И тому подобное.

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

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

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

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

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

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

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

    Например, к проблеме развязности может быть возведена обсуждаемая выше проблема проверки ривносильности заданных формул A и B.

    Легко доказать такую теорему.

    Теорема 1. Формулы алгебры высказываний A и B равносильные тогда и только затем, когда формула A B B A является тавтологией.

    С целью сокращения записи формул, подобных формуле из приведенной теоремы, к сигнатуре алгебры высказываний вводят дополнительную операцию, которая обозначается ~ и означається так, : A~ B является сокращенной записью формулы A B B A.

    Следовательно, последнюю теорему можно сформулировать так.

    Формулы A и B равносильные тогда и только затем, когда формула A~ B является тождественно истинной.

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

    Пусть A P1, P2.., Pn и B P1, P2.., Pn - две формулы алгебры высказываний. Будем говорить, что формула B P1, P2.., Pn есть Логическим следованием формулы A P1, P2.., Pn, если B принимает значение 1 для всех тех наборов значений пропозицийних переменных, для которых формула A истинная то есть принимает значение 1; будем помечать это A B.

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

    Пример 5.1. Формула B X, Y, Z= X Z является логическим следованием формулы A X, Y, Z= X Y Z, что выплывает из соответствующих таблиц истинности см. табл.4.

    Таблица 4

    X Y Z

    A B

    0 0 0

    0 0 1

    0 1 0

    0 1 1

    1 0 0

    1 0 1

    1 1 0

    1 1 1

    0 0

    0 1

    1 1

    Очевидно, что две формулы A и B является равносильными тогда и только затем, когда каждая из них является логическим следованием другой, то есть A= B тогда и только затем, когда A B и B A.

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

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

    Теорема 2. Формула B P1, P2.., Pn является логическим следованием формулы A P1, P2.., Pn тогда и только затем, когда тождественно истинной является формула A B.

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

    При построении алгебры высказываний исходными объектами были элементарные высказывания, которые имели определенное значение истинности, : 1 или 0. Новые объекты - составленные высказывания, которые также имели определенное значение истинности, - строились по четко определенным правилам образования формул. При этом значение истинности или ошибочности составленного высказывания определялось за таблицами истинности соответствующих операций алгебры высказываний. Отмеченные впоследствии понятия ривносильности и логического следования формул были введены содержательно, то есть с использованием значений истинности формул в зависимости от значений их переменных. Такое построение логического исчисления или теории называется Содержательно-алгоритмической, или Табличной.

    Iншим методом построения логического исчисления описан выше Формально-аксиоматический метод. Именно с помощью этого метода построено так называемое исчисление высказываний.