Глава 2. Математическая логика

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

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

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

Пример: «2x2=4» – истинное высказывание,

«Все студенты МГУКи владеют двумя языками» -- ложное высказывание,

«Да здравствует субботник» -- не высказывание.

Обозначают высказывания прописными буквами латинского алфавита x, y,z; истинностные значения – цифрами 0 (ложно) и 1(истинно).

Функции, аргументы и значения которых могут принимать только значения 0 и 1 называют булевыми функциями.

Операциями над высказываниями являются:

1) отрицание -- такое высказывание, которое истинно, когда x – ложно и наоборот.

-- отрицание (не x)

x

2) дизъюнкция (логическое сложение) – такое третье высказывание,

которое ложно в единственном случае: когда x и y оба ложны; в остальных случаях оно истинно.

-- дизъюнкция (x или y)

x	y

3) конъюнкция (логическое умножение) – такое третье высказывание, которое истинно лишь в одном случае, когда x и y оба истинны, в остальных случаях – ложно.

-- конъюнкция (x и y)

x	y

4) импликация (логическое следствие) – такое третье высказывание, которое ложно в единственном случае, когда x—истинно, а y – ложно. В остальных случаях -- истинно.

-- импликация (если x, то y)

x	y

5) эквиваленция (логическое равенство) – такое третье высказывание, которое истинно, когда x и y принимают одинаковые истинностные значения, в остальных случаях – ложно.

-- эквиваленция (тогда и только тогда)

x	y

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

n для отрицания скобки опускаются;

n имеет приоритет перед ;

n имеет приоритет .

Любая булева функция определяется своей таблицей истинности.

Пример: определим таблицу истинности булевой функции .

x	y

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

Пример: -- формула для исключения импликаций

Для установления равносильности формул, нужно составить таблицу истинности для левой и правой частей. Если истинностные значения совпадают, то формулы равносильны.

x	y

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

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

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

т.и.(т.л) – тавтологии – 1(0)

Любая тавтология выражает собой некоторый логический закон.

Пример: -- закон отделения

x	y

Число булевых функций от n переменных равно .

Пример: если n=1, то ;

Если n=2, то . Все они указаны в таблице:

У некоторых из этих функций есть специальные названия.

-- тождественный нуль.

-- конъюнкция. Часто знак не пишут ()

-- сложение по модулю 2.

-- дизъюнкция.

-- стрелка Пирса.

-- эквивалентность.

-- импликация.

-- штрих Шеффера.

-- тождественная единица.

Часто при задании булевой функции ограничиваются указанием ее набора значений. Например, .

Задачи.

1. Предположим, что высказываниям x, y, z и t соответствуют значения 1, 0, 0 и 1. Найти истинностные значения каждого из следующих высказываний:

a) ;

b) ;

c) ;

d) .

2. Пусть значение высказывания

a) истинно;

b) ложно.

Что можно сказать о значениях высказываний и ?

3. С помощью таблицы истинности доказать формулы:

а) -- исключение импликации;

b) -- исключение эквивалентности: .

4. С помощью таблицы истинности доказать законы:

a) -- закон силлогизма;

b) -- закон отделения;

c) -- закон контрапозиции.

2.2. Логика предикатов.

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

Пример: P(x)= «x – простое число» -- одноместный предикат, P(2)= «2 – простое число» -- истинное высказывание(1), P(4)= «4 – простое число» -- ложное высказывание(0).

Q(x,y)= «» -- двухместный предикат, Q(1,2)= «1>2; » -- ложное высказывание(0), Q(2,1)= «2>1; 2,1 » -- истинное высказывание(1).

Замена части предикатных неизвестных обращает его в предикат меньшей местности. Замена вех переменных – в высказывание. Высказывание при этом является 0-местным предикатом.

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

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

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

(для всех x) – квантор общности;

(существует такое значение x) – квантор существования.

Пример: P(x)= «x – простое число» -- одноместный предикат,

P(x) – истинное высказывание,

P(x) – ложное высказывание.

Если все предикатные переменные связаны кванторами, то предикат обращается в высказывание, если часть, то в предикат меньшей местности. Операция приписывания к предикату квантора называется навешиванием квантора. Переменная, к которой относится квантор, называется связанной, без квантора – свободной.

Пример: P(x,y,z)= «» -- трехместный предикат,

-- двухместный предикат,

-- одноместный предикат,

-- истинное высказывание.

Задачи.

1. Определить, чему равны значения предиката Р(x)= «x – четное число» при x=23 и x=48.
2. Применить кванторы общности и существования к предикату примера 1 и найти значения полученных высказываний.
3. Навесить квантор общности на все переменные предиката P(x,y)= «x делится на y без остатка» и определить значение высказывания.
4. Навесить квантор существования на все переменные предиката P(x,y)= «x делится на y без остатка» и определить значение высказывания.

2.3. Решение логических задач с помощью булевых функций.

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

Пример: Сергей, Анна, Юрий и Ольга заняли на математической олимпиаде четыре первых места. На вопрос о распределении мест, одноклассники ответили следующее: 1) Анна – первая, Ольга – вторая; 2) Анна – вторая, Сергей – третий; 3) Юрий – второй, Сергей – четвертый. В каждом из ответов только одно утверждение истинно. Определим, как распределились места.

Пусть -- простые высказывания, где X – первая буква имени участника. Y – номер занятого места. Тогда высказывания можно записать: 1) ; 2) ; 3) .

Так как все дизъюнкции истинны, то истинной будет и конъюнкция этих дизъюнкций, т.е.

()()()=1;

=1;

=0, т.к. Анна не может занимать два места;

=0, т.к. Ольга и Анна не могут обе быть на втором месте.

Тогда равенство примет вид: =1;

=1;

=1.

Следовательно, Анна заняла первое место, Сергей – второе, Юрий – третье, тогда Ольга – четвертое.

Задачи.

1. Записать символически следующие сложные предложения:

а) идет дождь или кто-то не выключил душ;

b) если вечером будет дождь, то Олег или останется дома, или должен будет взять такси;

c) если я устал или голоден, я не могу заниматься;

d) хлеба уцелеют тогда и только тогда, когда будут вырыты ирригационные канавы; если хлеба не уцелеют, то фермеры обанкротятся и оставят фермы.

2. Пусть даны высказывания: c= «сегодня ясно», r= «сегодня идет дождь», s= «сегодня идет снег», y= «вчера было пасмурно». Перевести на обычный язык следующие сложные высказывания:

a) ;

b) ;

c) .

3. Исследовать справедливость следующих рассуждений.

(а) Я пойду домой или останусь в университете и сдам долги. Я не пойду домой. Следовательно, я останусь и сдам.

(b) Заработная плата возрастет только, если будет инфляция. Если будет инфляция, то увеличится стоимость жизни. Заработная плата возрастет. Следовательно, увеличится стоимость жизни.

(с) Преподаватель или переутомился, или болен. Если он переутомился, то он раздражается. Он не раздражается. Следовательно, он болен.

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

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

(f) Встретились скульптор Белов, скрипач Чернов и художник Рыжов. «Замечательно, что один из нас имеет белые, один черные и один рыжие волосы, но ни у одного нет волос того цвета, на который указывает его фамилия», -- заметил черноволосый. «Ты прав», -- сказал Белов. Определить, какой цвет волос у художника.

Глава 3. Комбинаторика.

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

3.1.Общие правила комбинаторики.

Рассмотрим правило суммы.

Если некоторый элемент из одного множества можно выбрать n способами, а из другого -- m способами, то существует m+n способов выбора данного объекта из двух множеств.

Пример: Есть возможность добраться из пункта А в пункт В либо самолетом (три рейса в день), либо поездом (два рейса в день). Сколько существует вариантов отправления человека из пункта А в пункт В?

3+2=5 – вариантов. Это и есть правило суммы для непересекающихся множеств.

Если множества пересекаются, то число способов выбора объекта будет m+n-k, где k – элементы, лежащие одновременно в двух множествах.

Пример: Из двух магазинов нужно выбрать один товар. В первом магазине 5 видов подходящего товара, во втором – 10, причем среди 5-ти и 10-ти видов 3 одинаковых. Сколько существует способов выбора подходящего товара?

5+10-3=12 – способов.

Правило умножения.

Пример: Нужно добраться из пункта А в пункт С через пункт В. Из пункта А в пункт В ведут три дороги; из пункта В в пункт С – четыре. Найти все варианты маршрутов следования А–В--С.

3 4=12 вариантов.

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

Известно, что наименьшей расчетной единицей памяти ЭВМ является байт, состоящий из восьми бит – ячеек, в каждую из которых может быть помещены 1 или 0. Набор единиц и нулей может быть различным и в каждом отдельном случае составляет комбинацию. Для нахождения всех возможных комбинаций используется правило умножения. В первой ячейке возможны два варианта – 1 или 0. Каждому из вариантов первой ячейки соответствуют два варианта второй ячейки, т.е. . Продолжая далее, можно посчитать количество всех возможных комбинаций заполнения ячеек единицами и нулями: .

3.2.Перестановки.

Тридцать три буквы русского алфавита принято располагать от А до Я. Можно расположить в обратном порядке: от Я до А. Каждое расположение тридцати трех букв в определенном порядке называется их перестановкой. Количество всех таких перестановок выражается тридцатисемизначным числом.

Перестановки можно образовывать из элементов любого конечного множества.

Множество из одного элемента можно упорядочить одним-единственным образом. Множество из двух элементов А и Б – двумя способами: АБ и БА.

Множество из трех элементов: А, Б, В – шестью способами: АБВ, АВБ, БАВ, БВА, ВАБ, ВБА.

Установленный в конечном множестве порядок элементов называют перестановкой.

Число перестановок из n элементов обозначают через . Мы нашли, что

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

. (1)

Докажем ее. Пусть требуется упорядочить множество из n элементов. Какой-то из этих элементов придется поставить на последнее, n-е место. Этот элемент можно выбрать n различными способами. Если он уже выбран, то останется n-1 элемент. Ими придется занять первые n-1 мест. Это можно сделать способами (по смыслу ). Всего получается способов упорядочить множество из n элементов, т.е. .

По формуле (1) последовательно получаем:

Например, 7 гостей можно рассадить по 7 местам за столом 5040 способами.

Из формулы (1) вытекает, что (число перестановок из n элементов) равно произведению первых n натуральных чисел:

. (2)

Для произведения первых n натуральных чисел принято специальное обозначение: n! (читается «n-факториал»). Пользуясь этим обозначением, формулу (2) можно записать в виде

n! (3)

Для дальнейшего удобно считать, что пустое множество можно упорядочить только одним способом, т.е. . Тогда формулой (1) можно пользоваться и при n=1:

.

Пример: Сколькими способами можно составить список из 9 студентов?

=362880.

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

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

Пример: все перестановки для набора чисел (5,1,5): 515, 551, 155; все перестановки для набора чисел (5,1,2): 512, 521, 125, 152, 215, 251. В первом и втором наборах по три элемента, но там, где элементы повторяются, число перестановок меньше. Следовательно, число перестановок зависит от количества повторяющихся элементов.

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

Теорема. Число различных перестановок с повторениями определяется по формуле:

. (4)

Пример: разобьем набор чисел предыдущего примера (5,1,5) на группы: =2 – количество 5-ок и =1 – количество 1-ниц. Тогда по формуле (4): =3.

Задачи.

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

2. Сколькими способами можно составить список из 9 студентов?

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

4. Найти значение выражения:

а) 8! +9!; б) ; в) .

5.Сократить дробь:

а) ; б) ; в) .

6. Из цифр 0,1,2,3 составлены всевозможные четырехзначные числа так, что в каждом числе нет одинаковых цифр. Сколько получилось чисел?

7. Из цифр 1,2,3,4,5 составлены всевозможные пятизначные числа без повторения цифр. Выясните, сколько среди этих пятизначных чисел таких, которые:

а) начинаются цифрой 3;

б) не начинаются с цифры 5;

в) начинаются с 54;

г) не начинаются с 543.

8. Определить, сколько различных слов можно составить из слова «литература».

3.3.Размещения.

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

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

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

Каждое упорядоченное подмножество из m элементов множества из n элементов называется размещением из n элементов по m элементов -- («A из n по m»).

Теорема. Число размещений элементов множества определяется по формуле: .

Для доказательства данной формулы воспользуемся следующими рассуждениями: на первое место упорядоченного множества из m элементов можно поставить один из n элементов (таких вариантов n), на второе – один из (n-1) элементов (таких вариантов (n-1)). Итого n(n-1), т.к. каждому из n соответствует один из (n-1). Продолжая далее, на m место можно поставить один из (n-m+1). Получаем: .

Пример: Сколько различных размещений по 3 элемента из элементов множества можно составить?

.

Бывают случаи, когда элементы в m-подмножествах повторяются. Такие размещения называют размещениями с повторениями.

Теорема. Число размещений из n элементов множества по m с повторениями равно .

Действительно, поскольку осуществляется m выборов и каждый производится из n элементов, то по правилу произведения получаем .

Пример: Сколькими способами можно распределить 3 различных предмета между 5 лицами?

=125.

Задачи.

1. Доказать, что .

2. Сколькими способами можно выбрать четырех человек на четыре различные должности из девяти кандидатов на эти должности?

3. В группе 15 студентов. Они обменялись друг с другом фотокарточками. Сколько всего было роздано фотокарточек?

4. Найти n, если .

5. Какая часть из семизначных телефонных номеров состоит из семи различных цифр?

6. В однокруговом турнире по футболу участвуют 8 команд. Сколько существует вариантов призовой тройки?

7. Студенты первого курса изучают 15 предметов. Сколькими способами можно составить расписание на среду, если известно, что в этот день должно быть 6 пар?

8. Сколько различных слов из 3 букв можно составить из 33 букв алфавита?

9. Сколько существует вариантов назначения 5 исполнителей на выполнение 5 видов работ?

3.4. Сочетания.

Пример: Рассмотрим все подмножества множества . Их восемь:

-- пустое множество;

-- три множества по одному элементу в каждом;

-- три множества по два элемента в каждом;

-- одно множество из трех элементов.

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

Из примера видно, что и

.

Если число элементов множества большое, то процесс выписки всех подмножеств сложен. В этом случае число подмножеств определяется по формуле P(A)= . Выведем ее.

Перенумеровав все элементы множества А из примера, поставим в соответствие каждому подмножеству комбинацию 0 и 1, где присутствие элемента означает 1, отсутствие – 0. Т.е. -- 0,0,0;

-- 1,0,0;

-- 0,1,0 и т.д.

Таким образом, проблема о количестве подмножеств n-элементного множества А сводится к тому, сколько различных последовательностей длины n можно построить из 0 и 1. По правилу умножения, их число будет равно .

Чтобы вывести формулу для , докажем сначала, что .

Рассмотрим случай при m=2 и n=3. =3 – число множеств по две буквы в каждом. Каждое из них можно упорядочить способами, что дает упорядоченных множеств. Действительно, .

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

-- выделить какие-либо m из этих n элементов, что можно сделать способами;

-- упорядочить выделенные m элементы, что можно сделать способами.

Всего получим способов (упорядоченных множеств), т.е.

, что и требовалось доказать.

Из этой формулы несложно получить .

Подставляя сюда формулы и , получим:

.

Пример: Сколькими способами можно выбрать трех делегатов на конференцию из 35 студентов?

.

Основные свойства сочетаний:

;

;

;

.

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

Пример: в почтовом отделении продаются открытки 5 видов. Определить число способов покупки 7 открыток.

.

Теорема. Число сочетаний из n элементов по m c повторениями определяется по формуле .

Числитель (n+m-1) составляется таким образом потому, что каждому из сочетаний ставится в соответствии комбинация из m единиц и n-1 нулей, по которой в обратном порядке можно восстановить соответствующее сочетание. Знак факториала означает число всех возможных перестановок элементов этих комбинаций. В итоге формула числа сочетаний с повторениями соответствует формуле числа перестановок с повторениями , в которой n=n+m-1, .

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

Для положительного целого числа n справедлива формула, называемая биномом Ньютона:

, где -- биномиальные коэффициенты.

Пример: .

Задачи.

1. Составить все подмножества множества М и найти их число, если:

а) ; б) ; в) .

2. Сколько подмножеств содержит множество из 6 элементов?

3. Найти: а) ; б) ; в) .

4. Из 20 рабочих нужно выделить 6 для работы на определенном участке. Сколькими способами это можно сделать?

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

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

7. Студент имеет по одной монете достоинством 5 коп., 10 коп., 50 коп., 1 руб., 2 руб., 5 руб., 10 руб. Сколькими способами он может разложить эти монеты в два кармана?

8. Из 10 различных цветов нужно составить букет так, чтобы он состоял из не менее двух цветов разного сорта?

9. Имеется 12 различных конфет. Сколькими способами можно из них составить набор, если в наборе должно быть четное число конфет?

10. Сколько существует способов выбора в кондитерской шести пирожных из восьми их сортов?

11. Сколько костей домино можно сделать, используя 7 цифр?

12. Определить разложение при n=5.

Не нашли, что искали? Воспользуйтесь поиском: