Элементы математической логики

Размещено на http://allbest.ru

Министерство образования и науки Российской Федерации

Федеральное государственное автономное образовательное учреждение высшего образования

«Санкт-Петербургский политехнический университет Петра Великого»

Институт среднего профессионального образования

УТВЕРЖДАЮ:

Директор ИСПО

А.А. Гусаков

Методические рекомендации

по выполнению контрольной работы и практических работ

по предмету «Элементы математической логики»

Для студентов заочного отделения

09.02.03. «Программирование в компьютерных системах»

Разработчик: Ю.А. Муравьёва,

преподаватель ИСПО СПбПУ

Санкт-Петербург

2019 год



Методические рекомендации по выполнению контрольной работы и практических работ разработаны на основе Федеральных государственных образовательных стандартов (далее - ФГОС) по специальности среднего профессионального образования (далее - СПО) 09.02.03 «Программирование в компьютерных системах» и учебных планов ИСПО федерального государственного автономного образовательного учреждения высшего образования «Санкт-Петербургский политехнический университет Петра Великого».

Рекомендованы Методическим советом ИСПО СПбПУ

Старший методист О.М. Симонова

Зам. директора по УМР Е.Г. Конакина

Рассмотрены: предметной (цикловой) комиссией математики и физики

Председатель ПЦК Е.В. Кудрявцева



Пояснительная записка

Методические указания к выполнению внеаудиторной самостоятельной работы студентов по дисциплине «Элементы математической логики» предназначены для студентов заочного отделения 2-го курса по специальности 09.02.03. «Программирование в компьютерных системах».

Цель методических указаний: оказание помощи студентам в выполнении контрольной работы и практических работ по дисциплине «Элементы математической логики».

В результате изучения дисциплины студент

- Должен знать: основные принципы математической логики, теории множеств и теории алгоритмов;

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

методы минимизации алгебраических преобразований;

основы языка и алгебры предикатов.

- Должен уметь: формулировать задачи логического характера и применять средства математической логики для их решения.

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

- ОК 1 - Понимать сущность и социальную значимость своей будущей профессии, проявлять к ней устойчивый интерес.

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

- ОК 3 - Принимать решения в стандартных и нестандартных ситуациях и нести за них ответственность.

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

- ОК 5 - Использовать информационно-коммуникационные технологии в профессиональной деятельности.

- ОК 6 - Работать в коллективе и команде, эффективно общаться с коллегами, руководством, потребителями.

- ОК 7 - Брать на себя ответственность за работу членов команды (подчиненных), результат выполнения заданий.

- ОК 8 - Самостоятельно определять задачи профессионального и личностного развития, заниматься самообразованием, осознанно планировать повышение квалификации.

- ОК 9 - Ориентироваться в условиях частой смены технологий в профессиональной деятельности.

- ПК 1.1 - Выполнять разработку спецификаций отдельных компонент.

- ПК 1.2 - Осуществлять разработку кода программного продукта на основе готовых спецификаций на уровне модуля.

- ПК 2.4 - Реализовывать методы и технологии защиты информации в базах данных.

- ПК 3.4 - Осуществлять разработку тестовых наборов и тестовых сценариев.

Знания по дисциплине приобретаются студентами в процессе проведения занятий и в процессе самоподготовки.

Умения формируются при решении практических работ.

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

При выполнении контрольной работы студент должен руководствоваться следующими указаниями:

1. Контрольная работа выполняется в отдельной тетради в клетку, на титульном листе которой должны быть ясно написаны фамилия студента, его инициалы, курс, специальность, e-mail, сотовый телефон, домашний адрес.

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

3. На каждой странице тетради необходимо оставлять поля шириной 3-4 см для замечаний преподавателя.

4. Контрольная работа выполняется самостоятельно.

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

6. Студент выполняет тот вариант, который совпадает с его номером в журнале. Варианты контрольной работы представлены в приложении.

Перед выполнением контрольной работы студент должен изучить соответствующие разделы курса “Элементы математической логики”, используя учебные издания, Интернет-ресурсы, дополнительную литературу и составить конспект.

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

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

Требования к конспекту: системность, логичность изложения, краткость, убедительность и доказательность.

Этапы конспектирования:

1. Прочитайте текст, отметьте в нем непонятные места, новые термины, перечислите основные мысли текста, составьте план.

2. Выясните значение новых непонятных терминов и символов.

3. Вторичное чтение сочетайте с записями основных мыслей. Запись ведите своими словами, не переписывайте текст дословно.

Правила записи текста:

1. Запись должна быть компактной.

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

3. При записи допускается пользоваться сокращениями.

4. Сформулируйте и запишите вывод.

Цель написания контрольной (домашней) работы - оценить освоенные умения и усвоенные знания.

Порядок выполнения самостоятельной работы:



1. Основы теории множеств

Изучить по учебной литературе вопросы:

· Основные понятия теории множеств.

· Задание множеств.

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

· Свойства операций.

· Декартово произведение.

1.1 Основные понятия

I. Понятие «множество» принадлежит к числу простейших математических понятий. Оно не имеет определения, но может быть пояснено при помощи примеров.

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

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

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

.

Это означает, что x, y, z - элементы множества А.



Запись следует читать так: x, y, z - элементы некоторого множества. Если а есть элемент множества А, то говорят, что «элемент а принадлежит множеству А»; пишут аА.

Запись (или аА) означает, что элемент а не принадлежит множеству А.

Пример: пусть А={1; 7; 3}, тогда: 5 А (или 5{1; 7; 3}); 3 А.

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

1.2 Задание множеств

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

Такие свойства называются характеристическими.

Примеры:

пусть А={2; 3; 9}; множество А задано перечислением всех его элементов;

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

Если множество В состоит из всех элементов, обладающих определенным свойством, то пишут:



В={x: . . .} или В={x . . .};

знак”:” (или, что то же, “” ) читается, как «такие, что», «таких, что», «такой, что»; после этого знака пишут указанное свойство элементов множества В.

Пример: пусть множество В определено следующим образом:

(или )

буквальное чтение этой записи таково: «В - множество всех целых чисел х, таких, что каждое из них делится на 2» или короче: «В - множество четных чисел».

Вообще, если сказано, что множество А состоит из элементов с некоторым свойством, то это означает, что, во-первых, всякий «объект», обладающий этим свойством, принадлежит множеству А и, во-вторых, ни один «объект», не обладающий этим свойством, множеству А не принадлежит.

Множество называется пустым, если оно не содержит ни одного элемента (обозначение: ).

Пример.

Решить уравнение: х²+х+2=0;

D = -7; D<0; уравнение не имеет решений; иногда говорят, что множество корней уравнения пусто, при этом можно написать: {х}=.

Особое внимание следует обратить на то, что запись хєш является НЕВЕРНОЙ.

По определению пустому множеству не принадлежит ни один элемент.

Множества, состоящие из одних и тех же (из одинаковых) элементов, называются равными.

Число и порядок элементов при этом не важны. Если множества А и В равны, то пишут: А=В.

Пример. Пусть даны множества:

А={2;2;5}, В={2;2;5}, C={2;5;2}, D={2;2;5;5}, E={2;2;5;6}, F={-1;1/2}, G={5;2}.

Тогда: А=В, А=С, А=D, A?E, A?F, A=G.

Таким образом, множества А и В равны, если любой элемент множества А является элементом множества В и любой элемент множества В является элементом множества А.

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

Другими словами, если любой элемент множества В является и элементом множества А, то множество В называется подмножеством множества А.

В этом случае говорят, что В включается в А, и пишут: В С А.

По определению:

1) любое множество является подмножеством самого себя;

2) пустое множество считается подмножеством любого множества.

Если А В и А?В, то пишут А С В.

Например, можно записать: А С А, А=А, {а; с} С {а; в; с; d}.

Если А и В - квадраты, изображенные на рис.1, то АВ и даже АВ.

Рис.1

Таким образом, у любого множества А всегда есть два подмножества: А и Ш. Эти подмножества называются несобственными подмножествами множества А.

Любое подмножество В множества А, отличное от Ш и А, называется собственным подмножеством или правильной частью множества А.

Пример.

Пусть А={1;2;3}. Множества {1}, {2}, {3}, {1;2}, {1;3}, {2;3} являются собственными подмножествами множества А. Множества {1;2;3}и Ш являются несобственными подмножествами множества А.

Теорема (о числе подмножеств конечного множества). Пусть дано множество, содержащее n различных элементов. Тогда число всех подмножеств данного множества равно 2ⁿ.

Множество, в котором введен порядок, т.е. указано, какой элемент следует за каким, называется упорядоченным.

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

А={x₁;…;x_n}

Элементы упорядоченного множества перечисляют, записывая их в круглых скобках:

В=(x₁;x₂;…;x_n)

Примером упорядоченного множества являются координаты точки, неупорядоченного - множество птиц в стае.

1.3 Операции над множествами и их свойства

I. Пересечением множеств называется множество, все элементы которого принадлежат каждому из данных множеств (пересечение множеств - это их «общая часть»).

Пересечение множеств А и В обозначается так: . Если говорится о пересечении n множеств А₁, А₂,…, Аn, то пишут: .

Очевидно:

Примеры:

1. А={1;2;3;4}, B={2;4;6}; ;

2.

3. пересечение окружности и прямой-точки А и В;

4. ;

5. ;

6. (-;0)[-5;-3]=[-5;-3];

7. ;

8. ;

9. В={2n:nN}, A=N; АВ=В; следует обратить внимание, что если ВА, то АВ=В.

Два множества, пересечение которых является пустым множеством, называются непересекающимися (или дизъюнктными) множествами.

Примеры:

[1;5][6;7]=;

А=;

А={2n:nN}, B={2n-1:nN}; АВ=.

Для операции пересечения справедливы переместительный и сочетательный законы:

АВ=ВА;

А(ВС)=(АВ)С.

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

Объединение множеств А и В обозначается АВ. Если говорят об объединении n множеств, то пишут: А₁А₂…Аn.



Примеры:

1. А={2;4;6;…;2n}; B={1;3;5;…;2n-1}; nN; AB=N;

2. [1;+)[0;5]=[0;+);

3. (-;0)[-5;-3]=(-;0);

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

5. А=А;

6. АА=А.

Из определения объединения множеств следует, что если элемент принадлежит какому-то множеству, то он принадлежит и объединению этого множества с любым другим множеством, т.е.: хАх(АВ).

Пусть множества А и В не имеют общих элементов (т.е. АВ=). Если во множестве А содержится n элементов, а во множестве В содержится m элементов, то во множестве АВ

Содержится m+n элементов.

Пример: {1;2;3}{4;5}={1;2;3;4;5}.

Если множества А и В имеют общие элементы (т.е. АВ), то каждый из этих общих элементов берется во множестве АВ только один раз.

Пример: {1;2;3}{3;4}={1;2;3;4}.

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

А - количество элементов множества А (например, если А={3;8;9}, то А=3).

Тогда упомянутая выше формула имеет вид:



АВ=А+В-АВ.

Соответствующая формула для трех конечных множеств А,В,С будет выглядеть так:

АВС=А+В+С-АВ-АС-ВС+АВС.

III. Принцип двойственности

А(ВС)=(АВ)(АС) (1)

А(ВС)=(АВ)(АС) (2)

Эти равенства выражают так называемый принцип двойственности в частном случае трех множеств.

IV. Разность множеств. Разностью множеств А и В называется множество, состоящее из всех элементов множества А, не принадлежащих множеству В.

Обозначение: А\В (или А-В).

По определению:

А\В={x:xA и хВ}, т.е.

Примеры:

1. А={1;2;3;4}, B={1;2}; A\B={3;4};

2. A={1;2;3}, B={3;4;5;6}; A\B={1;2};

3. A={1;2;5}, B={3;4}; A\B={1;2;5};

4. A={1;2}, B={1;2;3}; A\B=;

5. [0;3]\[2;5]=[0;2);

6. {-1;2;3}\ (2;3)= {-1;2;3};

7. {-1;2;3}\ [-1;3)={3}.

Для того, чтобы найти разность А\В, очевидно, не требуется выполнение условия ВА. Из определения следует, что А\ВА.

V. Дополнение. Множество, которое содержит подмножествами все множества данной задачи, называется универсальным для указанных множеств. Например, для элементарной арифметики универсальным множеством является множество всех целых чисел; в элементарной алгебре, до введения комплексных чисел, универсальным множеством является множество всех вещественных чисел.

Пусть Y - некоторое фиксированное множество (универсальное), А - его подмножество.

Тогда дополнением множества А до Y называется множество, состоящее из всех тех элементов Y, которые не являются элементами множества А. Другими словами, дополнением данного множества А до универсального называется разность между универсальным множеством и множеством А.

Если рассматривают дополнение множества А до Y, то пишут: СyА (или СА, или Y\или В).

Пример:

1. Пусть Y={1;2;3;4;5}, тогда: ={2;4} (т.е. Cy{1;3;5}={2;4});

1.4 Операции над множествами: декартово произведение

I. Декартово произведение двух множеств. Прямым (или декартовым) произведением множеств А и В называется множество, элементами которого являются все упорядоченные пары (a;b), в которых первой компонентой является элемент из А, второй компонентой - элемент из В.

Прямое произведение множеств А и В обозначается АВ.

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

В={a;b}={b;a};

более того, в этом случае допускается даже дублирование:

В={a;b}={a;b;b;a}.

Но порядок перечисления элементов в круглых скобках важен: (1;а)(а;1).

Примеры:

1. А={0;1}, B={2;3}; AB={(0;2);(0;3);(1;2);(1;3)};

2. А={a₁;a₂;a₃}, B={b₁;b₂;b₃}; несколько элементов множества АВ:

(a₁;b₁), (a₂;b₂), (a₁;b₃),…;

3. А={тарелка; ложка; чашка};

В - множество расцветок; В=белая; красная; синяя;

АВ=белая тарелка; красная тарелка; синяя ложка;…;

4. А - множество цветов корпуса ручки;

В - множество цветов колпачка ручки;

А=белый; красный;

В=белый; черный; красный;

расцветки (белый; красный) и (красный; белый) - разные;

5. Прямая с уравнением y=2х+4 - это множество точек плоскости с координатами из множества {(x;2x+4):xIR}.

II. Прямым (декартовым) произведением множеств А₁, А₂,…, Аn называется множество А₁А₂…Аn, элементами которого являются все упорядоченные наборы (а₁;а₂;…;а_n), где а₁ - элемент из А₁, а₂ - элемент из А₂,…, а_n - элемент из Аn.

По определению:

А₁А₂…Аn={(a₁;a₂;…;a_n):a₁A₁, …, a_nAn}.

Если А₁=А₂=…=Аn, то множество А₁…Аn называется прямой (или декартовой) степенью множества А и обозначается через Аⁿ. Прямое произведение АА=А² называется декартовым квадратом.

Множество точек плоскости является по существу прямым произведением вида IRIR, где IR - множество действительных чисел. Поэтому на «геометрическом языке» элементы множества АВ называют точками (А - множество абсцисс, В - множество ординат).

Примеры:

А={1;2;3}, B={a;b}; C={0};

AB={(1;a);(1;b);(2;a);(2;b);(3;a);(3;b)};

BA={(a;1);(b;1);(a;2);(b;2);(a;3);(b;3)};

ABC={(1;a;0);(1;b;0);(2;a;0);(2;b;0);(3;a;0);(3;b;0)}; очевидно, что в общем случае АВВА, (АВ)СА(ВС);

Пусть А - современный русский алфавит; тогда множество АА - множество всех слов, состоящих из двух букв; для слов порядок букв важен; «он» и «но» - два различных слова; во множестве АА им соответствуют элементы (о;н), (н;о); безнаказанно дублировать буквы в слове нельзя: «он» и «оно» - разные слова; им соответствуют элементы (о;н)АА, (о;н;о)ААА.

Примеры решения задач рассмотрены на первом обзорном установочном занятии.

Пример 1: Пусть А={1; 7; 3}, тогда: 5 А (или 5{1; 7; 3}); 3 А.

Пример 2: Пусть А={1;2;3}. Множества {1}, {2}, {3}, {1;2}, {1;3}, {2;3} являются собственными подмножествами множества А. Множества {1;2;3}и Ш являются несобственными подмножествами множества А.

Пример 3: А={1;2;3;4}, B={2;4;6}; ;

Пример 4:

Пример 5: ;

Пример 6: ;

Пример 7: (-;0)[-5;-3]=[-5;-3];

Пример 8: ;

Пример 9: ;

Пример 10: В={2n:nN}, A=N; АВ=В; следует обратить внимание, что если ВА, то АВ=В.

Пример 11: {1;2;3}{4;5}={1;2;3;4;5}.

Пример 12: {1;2;3}{3;4}={1;2;3;4}.

Пример 13: А={1;2;3;4}, B={1;2}; A\B={3;4};

Пример 14: A={1;2;3}, B={3;4;5;6}; A\B={1;2};

Пример 15: A={1;2;5}, B={3;4}; A\B={1;2;5};

Пример 16: A={1;2}, B={1;2;3}; A\B=;

Пример 17: [0;3]\[2;5]=[0;2);

Пример 18: {-1;2;3}\ (2;3)= {-1;2;3};

Пример 19: {-1;2;3}\ [-1;3)={3}.

Пример20: Пусть Y={1;2;3;4;5}, тогда:={2;4}.

Пример21: Пусть Y=(-), тогда:

[2;3)=(-;2)[3;+); (-;-7]=(-7;+ ).

Пример21: А={0;1}, B={2;3}; AB={(0;2);(0;3);(1;2);(1;3)}.

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



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

Изучить по учебной литературе вопросы:

· Высказывания. Логические операции над высказываниями.

· Таблицы истинности.

· Понятие формулы логики, тождественно истинные и тождественно ложные формулы.

· Равносильность формул, свойства. Законы логики.

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

2.1 Высказывания. Логические операции над высказываниями

Рассмотрим несколько предложений:

“3 - простое число” - верное (истинное) предложение;

“4 - нечётное число” - неверное (ложное) предложение;

“Франция находится в Европе” - истинное предложение.

Определение: предложение (естественного языка или, например, математического), для которого имеет смысл говорить о его истинности или ложности, называется высказыванием.

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

Предложения “Решите задачу”, “Здравствуйте” не являются высказываниями (о них нельзя сказать, истинны они или ложны). Очевидно, высказываниями не являются повелительные или вопросительные предложения (говорить об их истинности или ложности нет смысла). Не являются высказываниями и такие предложения: “Каша - вкусное блюдо”, “Санкт-Петербург - самый красивый город в мире”, “Математика - интересная наука”; нет и не может быть единого мнения о том, истинны эти предложения или ложны. Предложение “Существуют инопланетные цивилизации” следует считать высказыванием, так как объективно оно либо истинное, либо ложное, хотя никто пока не знает, какое именно. Предложения “Шёл снег”, “Площадь комнаты равна 20 м²”, a² = 4 не являются высказываниями; для того чтобы имело смысл говорить об их истинности или ложности, нужны дополнительные сведения: когда и где шёл снег, о какой конкретной комнате идёт речь, какое число обозначено буквой a.

Далее будут использоваться буквы P, Q, …, возможно, с индексами, для обозначения высказываний (на самом деле эти переменные имеют своё название, см. §3).

Например:

P₁: “17<10³”

P₂: “= 3”;

P₃: “43 - простое число”;

P₄: “Июль - летний месяц”;

высказывания P₁, P₄, P₃ являются истинными, P₂ - ложным.

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

2.2 Таблицы истинности

I. Операция отрицания. Отрицание является простейшей логической операцией над высказываниями, соответствующее логической связке “не” (“неверно, что”).

Определение: отрицанием данного высказывания называется такое высказывание, которое истинно, если данное высказывание ложно, и ложно, если данное высказывание истинно.

Если над высказыванием Р выполнена операция отрицания, то пишут: читается “не Р”.

Примеры:

1) пусть Р: “6 - чётное число”, тогда : “6 - нечётное число”;

P - истинное высказывание, - ложное;

2) : “- целое число”; тогда : “- не целое число ”;

- ложное высказывание, - истинное;

3) : “Нева впадает в Финский залив”, тогда : “Нева не впадает в Финский залив”.

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

T	F
F	T

II. Конъюнкция высказываний. Сложное высказывание может быть составлено из простых с помощью союза “и”. Например, высказывание “Противоположные стороны любого прямоугольника равны и параллельны между собой” состоит из двух высказываний:

P₁: “Противоположные стороны любого прямоугольника равны между собой”;

P₂: “Противоположные стороны любого прямоугольника параллельны между собой”.

Союз “и” определяет логическую операцию, называемую конъюнкцией и обозначаемую символом .

Сложное высказывание, приведённое выше, записывается так:



P₁ P_2.

Таким образом, P₁ P₂ - конъюнкция двух высказываний (читается: “ P₁ и P₂”); P₁ и P₂ - члены конъюнкции.

Примеры:

1) Р₁: “На улице мороз -20⁰С”;

Р₂: “На улице идёт снег”;

P₁ P₂: “На улице мороз -20⁰С и идёт снег”;

P₁: “На улице мороз -20⁰С и снег не идёт”.

2) P₁: “3 > 2”;

P₂: “4 > 3”;

P₁ P₂: “3 > 2 и 4 > 3”;

конъюнкция P₁ P₂ может быть записана так: (3 > 2)(4 > 3);

P₂: “32 и 4 > 3”;

конъюнкция P₂ может быть записана следующим образом: (4 > 3); или (32)(4 > 3).

Определение: пусть имеются два высказывания P₁ и P₂; тогда высказывание, которое истинно в том и только в том случае, когда оба высказывания P₁ и P₂ истинны, называется конъюнкцией высказываний P₁ и P₂.

Это определение распространяется и на случай нескольких высказываний.

Аналогом знака конъюнкции является знак фигурной скобки. Запись

означает, что условия 5 > 3 и 0 < 1 должны быть выполнены одновременно. И соответствующая конъюнкция (5 > 3)(0 < 1) истинна в том и только в том случае, если истинны оба высказывания: 5 > 3 и 0 < 1.

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

P1	P2	P1 P2
T	T	T
T	F	F
F	T	F
F	F	F

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

III. Дизъюнкция высказываний. Если два высказывания соединены логической связкой “или”, то говорят о логической операции, называемой дизъюнкцией.

Определение: пусть даны два высказывания P₁ и P₂; тогда высказывание, которое истинно тогда и только тогда, когда истинно хотя бы одно из высказываний P₁, P₂, называется дизъюнкцией высказываний P₁ и P₂ и обозначается (читается “P₁ или P₂”); P₁, P₂ - члены дизъюнкции.

Это определение распространяется и на случай нескольких высказываний; оно закрепляет за союзом “или” неразделительный смысл.

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

Если даны высказывания P₁: “Число 2 - чётное”, P₂: “Число 2 -составное”, то дизъюнкция : “Число 2 - чётное или составное” является истинным высказыванием.

Примеры:

1) P₁: “15 > 9”; P₂: “2 > 9”;

: “15 > 9 или 2 > 9”; высказывание - истинное высказывание; оно может быть записано следующим образом:

;

NB! здесь не утверждается, что истинны оба высказывания: P₁ и P₂; это соответствовало бы конъюнкции; утверждается, что дизъюнкция истинна, если истинно хотя бы одно из высказываний; 15 > 9 - истинное высказывание, поэтому истинна и дизъюнкция ;

2) P₁: “7 < 10”; P₂: “7 = 10”;

дизъюнкция - истинное высказывание; в курсе алгебры дизъюнкция этих высказываний записывается в виде нестрогого неравенства ; это неравенство является верным, так как означает, что 7 либо меньше, либо равно 10;

NB! аналогом знака дизъюнкции является знак квадратной скобки; запись

читается так: “7 > 10 или 7 = 10”; она означает, что требуется выполнение хотя бы одного из условий, стоящих под знаком скобки.

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

P1	P2
T	T	T
T	F	T
F	T	T
F	F	F

Дизъюнкцию иногда называют логической суммой.

IV. Импликация высказываний. Два высказывания могут быть связаны при помощи слов “если …, то …”. Высказывание, идущее после слова “если” до слова “то”, называется условием (посылкой), а высказывание, следующее за словом “то, - заключением (следствием).

Определение: импликацией двух высказываний Р₁ и Р₂ называется такое высказывание (читается: “из Р₁ следует Р₂” или “если Р₁, то Р₂”), которое ложно тогда и только тогда, когда Р₁ истинно, а Р₂ ложно.

Принятое определение импликации соответствует употреблению союза “если …, то …” не только в математике, но и в обыденной речи. Вместе с тем определение импликации вынуждает считать истинными высказываниями такие предложения, как “Если , то Москва столица России” или “Если , то Земля имеет форму куба”. Эти предложения кажутся бессмысленными. Как правило, в обыденной речи считается, что если высказывание Р₁ ложно, то высказывание “Если Р₁, то Р₂ ” вообще не имеет смысла. Но определениями логических операций смысл высказываний никак не учитывается; они рассматриваются как объекты, обладающие единственным свойством - быть истинными или ложными. Смысл высказываний в математической логике не рассматривается.

Согласно определению импликации можно составить следующую таблицу истинности:

Р1	Р2
T	T	T
T	F	F
F	T	T
F	F	T

Правый член импликации называется антецедентом, второй - консеквентом.

V. Двойная импликация высказываний (эквивалентность, эквиваленция). Различные утверждения конструируются с помощью слов:

“если и только если”;

“те и только те”;

“тогда и только тогда”;

“необходимо и достаточно”.

Сложное высказывание, образованное из двух (или нескольких) высказываний при помощи вышеуказанных слов, является двойной импликацией высказываний и обозначается ; читается: “ Р₁ тогда и только тогда, когда Р₂” или “ Р₁ равносильно Р₂”, или “ Р₁ эквивалентно Р₂”.

Определение: двойной импликацией (эквиваленцией, эквивалентностью) высказываний Р₁ и Р₂ называется такое высказывание , которое истинно тогда и только тогда, когда оба высказывания Р₁ и Р₂ истинны или ложны одновременно.

Таблица истинности двойной импликации:

Р1	Р2
T	T	T
T	F	F
F	T	F
F	F	T

Например, говоря “Я поеду в Москву тогда и только тогда, когда ты поедешь в Киев”, мы утверждаем, что либо произойдёт и то, и другое, либо не произойдёт ни того, ни другого.

Формулы логики. Пусть A - некоторая формула логики высказываний. Если каждой переменной, входящей в эту формулу, приписать одно из значений истинности («T» или «F»), то, пользуясь определениями логических операций, можно найти значение формулы A при данном наборе значений ее переменных. Удобной формой записи при нахождении значений формулы, соответствующих всевозможным наборам значений ее переменных, является таблица истинности.

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

P	Q				(
T	T	F	T	F	F
T	F	F	F	T	T
F	T	T	T	F	F
F	F	T	T	T	T

Первые два и последний столбец этой таблицы выражают соответствие между всевозможными наборами значений переменных и значениями данной формулы.

Очевидно, что таблица истинности для формулы с четырьмя переменными содержит 16 строк; дляформулы с n переменными она содержит 2ⁿ строк.

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

2.3 Понятие формулы логики, тождественно истинные и тождественно ложные формулы

Основной задачей логики высказываний является установление истинностного значения формулы, если даны истинностные значения входящих в неё переменных.

Определение:

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

2. Если и -- формулы алгебры высказываний, то выражения также являются формулами алгебры высказываний:

3. Никаких других формул алгебры высказываний, кроме получающихся согласно пунктам 1 и 2, нет.

Тождественно истинные формулы. Формула называется тождественно истинной (или тавтологией), если эта формула принимает значение «T» (истина) при всех значениях входящих в нее переменных. Формула называется тождественно ложной (или противоречием), если она принимает значение «F» (ложь) при всех значениях входящих в нее переменных.

Составив таблицу истинности, всегда можно установить, является ли данная формула тождественно истинной или тождественно ложной.

2.4 Равносильность формул, свойства. Законы логики

I. Равносильность формул. Две формулы логики высказываний А и В называются равносильными, если их эквивалентность - тавтология.

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

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

Равносильность двух формул логики высказываний обозначается символом “”; запись читается так: “формула А равносильна формуле В”.

Выражение - не формула в языке логики высказываний. Равносильность есть отношение между формулами (так же как равенство - это отношение между числами, параллельность - это отношение между прямыми и т.п.).

Отношение равносильности обладает следующими свойствами:

1) (свойство рефлексивности);

2) если , то (свойство симметричности);

3) если и, то (свойство транзитивности).

Законы логики. Упрощение формул логики с помощью равносильных преобразований. Равносильность формул логики высказываний часто называют законами логики. Наиболее важные равносильности можно разбить на три группы.

1. Основные равносильности:

1) - закон тождества (утверждает, что мысль, заключённая в некотором высказывании, остаётся (считается) неизменной на протяжении всего рассуждения, в котором это высказывание фигурирует);

2) ; - законы идемпотентности (в силу этих законов в алгебре логики нет “показателей степеней” и “коэффициентов”);

3) ;

4) ;

5) ;

6) ;

7) - закон противоречия (говорит о том, что никакое высказывание не может быть истинным одновременно со своим отрицанием);

8) - закон исключения третьего (говорит о том, что для каждого высказывания есть лишь две возможности: это высказывание истинно или ложно, третьего не дано);

9) - закон (снятия) двойного отрицания;

10) ; - законы поглощения.

2. Равносильности, выражающие одни логические операции через другие:

1) ;

2) ;

3) ;

- законы де Моргана (выражаются в кратких словесных формулировках: отрицание конъюнкции равносильно дизъюнкции отрицаний; отрицание дизъюнкции равносильно конъюнкции отрицаний);

4) ;

5) .

Равносильности 4) и 5) получаются из равносильностей 3); если от обеих частей первого закона де Моргана взять отрицания и воспользоваться законом двойного отрицания, то получится равносильность 4); из второго закона де Моргана получается равносильность 5).

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

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

3. Равносильности, выражающие коммутативность, ассоциативность, дистрибутивность:

1) - коммутативность конъюнкции;

2) - коммутативность дизъюнкции;

3) - ассоциативность конъюнкции;

4) - ассоциативность дизъюнкции;

5) - дистрибутивность конъюнкции относительно дизъюнкции;

6) - дистрибутивность дизъюнкции относительно конъюнкции.

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

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

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

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

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

Примеры:

1) доказать равносильность:

;

запишем цепочку равносильных формул:



при равносильных переходах использовались законы:

(1) - закон 1) группы 2.;

(2) - закон 2) группы 2.;

(3) - закон 5) группы 3.;

(4) - закон противоречия, группа 1.;

(5) - закон 6) группы 1.;

(6) - закон 1) группы 3.;

2) упростить формулу ;

запишем цепочку равносильных формул:

при равносильных переходах использовались законы:

(1) - закон 2) группы 2. (для высказываний и );

(2) - закон двойного отрицания, группа 1.;

(3) - второй закон идемпотентности, группа 1.;

(4) - закон 1), группа 3.;

(5) - первый закон поглощения, группа 1.;

Примеры решения задач рассмотрены на втором обзорном установочном занятии.

Пример 1: Установить, истинно или ложно высказывание:

1) 2{x: 2x³ - 3x² + 1 = 0, xR};

2) -3{x: , xR};

3) {1}N;

4) {1}N;

5) ШШ;

6) Ш{Ш};

7) {1;-1;2}{x: x³ + x² - x - 1 = 0, xZ}

8) {x: x³ + x² - x - 1 = 0, xZ}{1;-1;2};

9) ШN;

10) { Ш}{ Ш;{ Ш}}.

Пример 2: 1) Р₁: “На улице мороз -20⁰С”;

Р₂: “На улице идёт снег”;

P₁ P₂: “На улице мороз -20⁰С и идёт снег”;

P₁: “На улице мороз -20⁰С и снег не идёт”.

2)P₁: “3 > 2”;

P₂: “4 > 3”.

Пример 3: составить таблицу истинности, соответствующую высказыванию .

Решение:

P1	P2
T	T	F	F
F	F	T	F
T	F	T	T
F	T	F	F

1) даны два высказывания (P₁ и P₂), поэтому первые два столбца заполняются в соответствии с тем, что каждое из высказываний может быть либо истинным, либо ложным;

2) далее число столбцов определяется количеством операций, произведённых над высказываниями; первая операция - операция отрицания для высказывания P₂; ей соответствует третий столбец;

3) вторая операция - конъюнкция высказываний P₁ и; ей соответствует четвёртый столбец; он заполняется в соответствии с определением конъюнкции.

Пример 4: составить таблицу истинности, соответствующую высказыванию .

Решение: даны три высказывания, каждое из которых либо истинно, либо ложно, требуется рассмотреть каждый из возможных случаев; для простоты перебора можно зафиксировать значение “истина” высказывания Р₁ и рассмотреть всевозможные комбинации значений “и”, “л” для высказываний Р₂ и Р₃; при этом получаются четыре варианта; аналогично, фиксируя значение “ложь” высказывания Р₁, получаем ещё четыре возможности; таким образом, всего восемь строк; далее - см. предыдущее упражнение.

P1	P2	P3	P1 P2
T	T	T	T	T
T	F	F	F	F
T	F	T	F	F
T	T	F	T	F
F	F	F	F	F
F	T	T	F	F
F	T	F	F	F
F	F	T	F	F

Пример 5: составить таблицу истинности, соответствующую высказыванию .

Решение:

P1	P2	P3
T	T	T	F	F	T
T	F	F	T	T	T
T	T	F	F	F	F
T	F	T	T	T	T
F	T	T	F	F	T
F	F	F	T	F	F
F	T	F	F	F	F
F	F	T	T	F	T

Пример 6: рассмотрим высказывание:

“Если 6 - чётное число, то 6 делится на 2”; оно является импликацией двух высказываний:

Р₁: “6 - чётное число”, Р₂: “6 делится на 2”;

Следующие высказывания истинны:

1) если 6 - чётное число, то 6 делится на 2;

2) если 6 - нечётное число, то 6 не делится на 2;

3) если 6 нечётное число, то 6 делится на 2;

и только высказывание “Если 6 - чётное число, то оно не делится на 2” является ложным.

Примеры решения задач рассмотрены на втором обзорном установочном занятии.

После изучения теории и решения примеров по данной теме можно решить задание №2 и №3 контрольной работы.



3. Булевы функции

Изучить по учебной литературе вопросы:

· Понятие булева вектора и булевой функции.

· Способы задания булевой функции.

· Приведение функции к совершенной ДНФ.

· Приведение функции к совершенной КНФ.

· Минимизация булевой функции. Метод карт Карно.

· Двоичное сложение. Полином Жегалкина.

3.1 Понятие булева вектора и булевой функции

Рассмотрим упорядоченный набор из n произвольных чисел. Слово «упорядоченный» означает, что элементы этого набора занумерованы, они занимают вполне определённые места в наборе, т.е., например, наборы (5; 3; 7; 11) и (3; 5; 7; 11) различны, хотя и состоят из одинакового количества и из одних и тех же чисел. Каждый из приведённых наборов - элемент прямого произведения. Упорядоченный набор чисел обычно называют вектором. Упорядоченный набор называется n-мерным булевым вектором, если

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

На рисунке изображены одномерный (n = 1(а)), двумерный (n = 2; (б)) и трёхмерный (n = 3; (в)) кубы.



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

Например, формула является функцией трёх переменных f(x;y;z). Особенностью этой функции является то обстоятельство, что её аргументы принимают одно из двух значений: ноль или единицу, и при этом функция также принимает одно из двух значений: ноль или единицу.

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

3.2 Способы задания булевой функции

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

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

х1	х2	х3	f(х1; х2; х3)
0	0	0	0
0	0	1	1
1	1	1	0
1	1	0	0
0	1	0	1
0	1	1	1
1	0	0	0
1	0	1	1

Табличный способ задания функции трёх пере¬мен¬ных f ( ; ; ) представлен таблицей. Например, на наборе (0; 0; 1) (т.е., если переменные , , принимают соответственно значения (0,0,1) функция принимает значение 1, а на наборе (1; 0; 0) - значение 0.

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

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

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

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

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

Как и в алгебре высказываний, для сокращения записи иногда опускают знак конъюнкции, условившись под выражением xy подразумевать выражение . Так, например, функция f(x; y; z) = может быть записана в виде f(x; y; z) = .

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

Примеры:

Для булевых выражений справедливы все законы логики, доказанные ранее.

Таким образом, всякая формула алгебры логики есть функция алгебры логики. Тождественно истинные и тождественно ложные формулы алгебры логики представляют собой постоянные функции ( - тождественно истинная формула; f(x) = - постоянная функция), а две равносильные формулы выражают одну и ту же функцию.

Число различных функций алгебры логики n переменных равно . В частности, различных функций одной переменной 4, а различных функций двух переменных 16. Рассмотрим функции алгебры логики одной и двух переменных.

Начнём с функции одной переменной f(x). Аргумент х может принимать одно из двух значений: 0 или 1. При этом функция f(x) может принимать либо только значение 1, либо только значение 0, либо разные значения. В последнем случае возможны два варианта. Тогда вышеизложенное может быть обобщено в виде таблицы истинности для различных функций одной переменной.

х
1	1	1	0	0
0	1	0	1	0

Из этой таблицы следует, что две функции одной переменной будут постоянными:

= 1, = 0.

Каждое значение функции совпадает с соответствующим значением переменной х, а каждое значение функции является отрицанием соответствующего значения аргумента, поэтому: = х, =.

Пусть теперь дана функция двух переменных f(x;y). Как отмечалось выше, число различных функций двух переменных равно 16. Рассмотрим некоторые их них.