Понятие высказывания, простые и составные высказывания

Каждая математическая дисциплина имеет свою собственную область объектов, которую она изучает. Например, геометрия изучает геометрические фигуры, математический анализ изучает функции, арифметика — числа. Основным объектом изучения алгебры высказываний, алгебры логики или Булевой алгебры являются высказывания.

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

Например: 20 > 5

Москва — столица России

Берлин — один из крупнейших городов Франции

Сколько Вам лет? — это не высказывание.

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

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

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

Единственное свойство элементарного высказывания, изучаемое в алгебре логики, является его истинностное значение. Никакого другого, конкретного содержания элементарное высказывание не имеет.

Операции на множестве высказываний.

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

Функция называется n—местной булевой функцией, если каждая переменная принимает только два значения 0 или 1 и функция принимает значения в этом же множестве {0;1}.

Отрицание.

Определим унарную логическую операцию — отрицание. Для этой операции таблица истинности выглядит следующим образом:

Иллюстрацией отрицания в естественном языке служит частица "не", или слова "неверно, что".

Например: если мы хотим отрицать, что

Точка М принадлежит прямой а (1)

Мы скажем

Точка М не принадлежит прямой а (2)

Если (1) — это высказывание, то (2) -

Обратите внимание, что истинностные значения высказываний (1) и (2) находятся в определенной зависимости: если (1) — истинно, то (2) — ложно.

Если (1) — ложно, то (2) — истинно.

Например, покажем, что

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

Конъюнкция

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

Свойства конъюнкции:

В естественном языке эта операция чаще всего интерпретируется союзом "и"

Дизъюнкция

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

 

4. "Исключающее или"

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

Импликация

Следующая логическая операция, которую мы рассмотрим — это операция импликации. Импликация ложна тогда и только тогда, когда — истинна, а — ложна.

Эквивалентность

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

В математических терминах эта операция интерпретируется в качестве фраз "тогда и только тогда", "необходимо и достаточно". Такая форма тоже очень часто используется в формулировке теорем. Эквивалентность представляется в виде:

Штрих Шеффера

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

Основные определения теории множеств. Примеры.

Понятие множества является одним из фундаментальных понятий математики, которому трудно дать определение. Дело в том, что определить понятие — это значит найти такое родовое понятие, в которое это понятие входит в качестве вида, но понятие «множество» - это самое широкое понятие математики и математической логики, т.е. категория, а для категории нельзя найти более широкое, т.е. родовое понятие. Ограничимся описательным объяснением этого понятия.

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

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

Какова же структура множества, чем одно множество отличается от другого, какие математические и логические операции определены для множества?

Прежде всего, каждое множество состоит из того или иного набора объектов, которые называются элементами множества.

Факт, что элемент а принадлежит множеству Х мы будем обозначать: а Î Х.

 

Порядок элементов в множестве несущественен. Множества { а, в, с } и { а, с, в } одинаковы.

Множество может задаваться:

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

2. путем описания свойств, общих для всех элементов этого множества, и только этого множества. Это свойство называется характеристическим свойством, а такой способ задания множества описанием. Таким образом, можно задавать как конечные, так и бесконечные множества. Если мы задаем множество каким-либо свойством, потом может оказаться, что этим свойством обладает всего лишь один объект или вообще такого объекта нет. Данный факт может быть совсем не очевиден.

Например:

множество натуральных чисел, больших 1, таких что, уравнение

имеет решение в ненулевых целых числах. Это множество содержит единственный элемент 2, но есть ли у него еще элементы, никто не знает.

Если характеристическим свойством, задающим множество. А не обладает ни один объект, то говорят, что множество А пустое. Обозначается это так: Æ.

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

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

пустое.

Множества бывают конечными или бесконечными. Если число элементов множества конечно — множество называется конечным.

Определение: Количество элементов, составляющих множество, называется мощностью множества.

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

Например:

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

множество чисел, делящихся без остатка на 3 — счетное множество,

множество букв русского алфавита, множество отличников вашей группы — конечно.

Определение: Два множества равны между собой, если они состоят из одних и тех же элементов. Т.е. любой элемент множества Х является элементом множества Y, и любой элемент множества Y является элементом множества Х.

Тема 2.2 Подмножество. Понятие универсального множества.

Подмножество

Определение: Множество Х является подмножеством Y, если любой элемент множества Х принадлежит множеству Y. Это еще называется нестрогим включением.

Некоторые свойства подмножества:

1. ХÍХ - рефлективность

2. X Í Y & YÍZ ® X Í Z - транзитивность

3. Æ Í X т.е. пустое множество является подмножеством любого множества.

Универсальное множество

Определение: Универсальное множество — это такое множество, которое состоит из всех элементов, а так же подмножеств множества объектов исследуемой области, т.е.

1. Если М Î I, то М Í I

2. Если М Î I, то Ώ(М) Í I, где под Ώ(М) — понимаются все возможные подмножества М, или Булеан М.

Универсальное множество обычно обозначается I.

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

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

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

Тема 2.3 Операции над множествами.

Теперь определим операции над множествами.

Пересечение множеств.

Определение: Пересечением множеств Х и У называется множество, состоящее из всех тех, и только тех элементов, которые принадлежат и множеству Х и множеству У.

Например: Х={1,2,3,4} У={2,4,6} пересечением {2,4}

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

Например: непересекающимися множествами являются множества отличников группы и неуспевающих.

Данную операцию можно распространить и на большее чем два число множеств. В этом случае это будет множество элементов, принадлежащих одновременно всем множествам.

Свойства пересечения:

1. X∩Y = Y∩X - коммутативности

2. (X∩Y) ∩Z =X∩ (Y∩Z)=X∩Y∩Z - ассоциативности

3. X∩Æ = Æ

4. X∩ I = Х

Объединение множеств

Определение: Объединением двух множеств называется множество, состоящее из всех и только тех элементов, которые принадлежат хотя бы одному из множеств Х или У.

Например: Х={1,2,3,4} У={2,4,6} объединением {1,2,3,4,6}

Данную операцию можно распространить и на большее чем два число множеств. В этом случае это будет множество элементов, принадлежащих хотя бы одному из этих множеств.

Свойства объединения:

1. XUY= YUY- коммутативности

2. (X UY)UZ =XU (YUZ)=XUYUZ - ассоциативности

3. XUÆ = X

4. XU I = I

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

Разность множеств

Определение: Данная операция, в отличие от операций пересечения и объединения определена только для двух множеств. Разностью множеств Х и У называется множество, состоящее их всех тех и только тех элементов, которые принадлежат Х и не принадлежат У.

Например: Х={1,2,3,4} У={2,4,6} разность {1,3}

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

Дополнение множества

Дополнением множества Х называется разность I и Х.

Свойства дополнения:

1. Множество Х и его дополнение не имеют общих элементов

2.Любой элемент I принадлежит или множеству Х или его дополнению.