Проверка, что формула является логическим следствием.

Билет 1

Множество – совокупность элементов, которые понимаются как единое целое.

A = B ó A и B содержат одинаковые элементы

A B ó A – подмножество B (т.е. все элементы A являются элементами B);

Если A содержит B и B A ó A = B (A={1;2} и B={1;2;2}) = > A=B

Если элемент указывается более 1 раза, то повторы можно отбросить

Булеан – множество всех подмножеств определенного множества ( A))

A = {1;2;3} => = { {1}; {2}; {3}; {1,2}; {1,3}; {2,3}; {1,2,3}}

|A|=n – число элементов множества (мощность множества)

= 2ⁿ – число булеанов

Универсальное множество – множество, состоящее из всех элементов и подмножеств множества

Операции:

объединение (+)

пересечение (*)

\ — разность

- дополнение

 

Билет 2

Свойства операций над множествами

коммуникативность операций

закон поглощения

ассоциативность

дистрибутивность

- двойственные выражения

 

Билет 3

Упорядоченная пара – два элемента, для которых указано какой является первым, а какой вторым

При этом <- равенство упорядоченных пар

Декартово произведение – множество упорядоченных пар, где:

A*A = A² — декартовый квадрат

бинарное отношение, если A². Смысл бинарных отношений – обозначение известных отношений между двумя объектами

 

Билет 4

Отношения эквивалентности — ситуация, когда p на множестве A рефлексивно, симметрично и транзитивно

Разбиение множеств: пусть А – множество, тогда семейство A₁, A₂,.., A_n ­— разбиение множества А, если

1. => объединение подмножеств A = множеству A

2.для

Класс эквивалентности: для , где — отношение эквивалентности

1. ([a] – класс)(следует из рефлексивности)

2. <-классы равны

(следует из транзитивности и симметричности)

Лемма: любые 2 класса эквивалентности либо не пересекаются, либо совпадают

Док-во: #

Теорема: любое отношение эквивалентности на А задает разбиение A на классы эквивалентности (верно и обратное) -> для любого разбиения множества А можно определить отношение , которое соответствует данному разбиению

Док-во: пусть – разбиение А -> определим отношение следующим образом:

1.рефлексивность:

2.симметричность: очевидно

3.транзитивность: т.к. b лежит в единственном множестве, то

 

Билет 5

Частично упорядоченные множества: пусть А – множество, если транзитивно, рефлексивно и антисимметрично, то – отношение частичного порядка, а А — ч.у.м.

Диаграмма ч.у.м. (для

Сравнимые и несравнимые элементы: элементы a и b — сравнимые, если или

Иначе они несравнимы (вместо можно использовать )

Если все элементы сравнимы -> диаграмма становится цепью типа ….

А ч.у.м. становится линейно упорядоченным множеством (л.у.м.)

Элемент — минимальный, если для из того, что ()

Элемент — максимальный, если для ) (пример перерисовать)

Лемма: пусть b ч.у.м. a – наиб/наим. Элемент => a – единственный макс/мин элемент

Док-во: (от противного) пусть есть еще один макс.элемент

 

Билет 6

Отображение (функция) из x в y — правило (соответствие), которое каждому ставит в соответствие однозначно определенный

Для f(x) — образ

Для f(x) = — образ множества А

Пример:

A = {x₃, x₄}, f(A) = {y₃} B = {x₁, x₃}, f(B) = {y₁, y₃}, f(x₁) = y₁

f: x -> y

Для — прообраз элемента y

Если , то — прообраз множества С

Примеры рисуйте сами

Билет 7

Отображение является:

Сюръективным, если

Инъективным, если

Биективным, если оно сюръективно и инъективно

Отображение f: x -> y тогда имеет обратное, когда оно биективно

Билет 8

Если f — сюръекция, то

Если f — инъекция, то

Если f — биекция, то

Билет 9

Композиция отображений: пусть f – отображение множества А во множестве В, g – отображение множества В во множестве С => композиция отображения f и g — это отображение , которое сопоставляет любому элементу элемент

Ассоциативность композиции:

Док-во:

(1) и (2) равны => ассоциативность доказана

Тождественное отображение: пусть X – произвольное множество. Тогда тождественное отображение X на X представляет собой функцию:

Композиция биективного с обратным: если f – биективно, то – отображение и

Множество отображений: пусть А и В – произвольные множества. Отображением множества А во множество В называют правило, которое каждому элементу множества А ставит в соответствие единственный для этого элемента элемент множества В

Композиция отображения с тождественным:

Билет 10

Операция (на А) – отображение f: A x A -> A для множества А

Примеры:

1) (для операции сложения) 2+3=5

2) (для операции умножения) 3*0=0 4*1=4

3) (можно ли рассмотреть операцию разности?)

Наиб. т.к.

 

Билет 11

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

1)

2)

3)

4)

Пример:

Билет 12

*

*опр. (А, ×)

Если × ассоциативно, есть нейтр.элем, и есть обр.элемент, то (А,×) – является группой

если × - коммутативна, то (А, ×) — коммутативна (абелева группа)

*пусть Х – множество, M a p (X) – множество всех отображений из Х в Х

B(x) – множество всех биективных отображений

 

Билет 13

Опр. мн-во R с операциями

+ и * называется кольцом, если абелева группа по сложению ассоциативна, коммутативна, имеет нейтральный и обратный член

(R, +, *) – кольцо

Если к кольцу добавить:

А) +4` (а*b=b*a), то получим коммутативное кольцо

Б) +2` (есть единичный элемент, a*1=1, a=a), то получим кольцо с единицей

В) +2`, 3`, 4` (2`: есть ед.элемент a*1=1*a=a

3`: для всех

4`: )

То получим поле

Билет 14

Высказывание – это любое повествовательное предложение, про которое можно сказать истинно оно или ложно

0 — «ложь» 1 — «истина»

x, y — логические переменные (т.е. переменные принимающие одно из двух значений, указанных выше)

Основные логические операции (связки):

1. Дизъюнкция —

2. Конъюнкция —

3. Отрицание —

4. Импликация —

5. Эквиваленция —

Определение: если x₁, x₂,.., x_n — логические переменные, то выражение F(x₁,x₂,.., x_n), которое на каждом наборе значений принимает значение 0 или 1, называется формулой высказываний или булевой функцией. Пример F(x,y,z,) =

Таблицы истинности — таблица, описывающая булеву функцию

Билет 15

Пусть x,y,z – логические переменные

Формулы:

Формулы логики высказываний (понятие)

1. Элементарные формулы

2. Если F и G – формулы, то тоже являются формулами логики

Билет 16

Условие истинности элементарной конъюнкции

Дизъюнкция элементарных конъюнкций называется дизъюнктивно-нормальной формой (ДНФ)

Пример:

1. – ДНФ 3. – не ДНФ

2.x –ДНФ 4. – не ДНФ

Алгоритм приведения к ДНФ:

1.Избавляемся от эквиваленции (<->) и импликации (->)

2.С помощью законов де-Моргана заносим отрицание к переменным

3.Раскрываем скобки (с помощью дистрибутивности и ассоциативности выносим все дизъюнкции наружу)

4.Упрощаем преобразования (необязательно)

Билет 17

СДНФ – это такая ДНФ, которая удовлетворяет двум условиям:

1.в ней нет одинаковых элементарных конъюнкций

2.в каждой конъюнкции нет одинаковых

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

Примеры

Теорема о приведении к СДНФ: любая выполнимая формула может приводиться к СДНФ

Алгоритм:

1 способ: строим таблицу истинности и находим строки с 1,

2 способ: строим ДНФ, к каждой конъюнкции добавляем нужный элемент

Билет 18

Выражение – элементарная дизъюнкция

КНФ – конъюнкции элементарных дизъюнкций

1. – КНФ

Алгоритм приведения к КНФ:

1)избавляемся от эквиваленции и импликации

2)применяем закон де-Моргана

3) и упростить

СКНФ – это такая КНФ, которая удовлетворяет условиям:

1.в ней нет одинаковых элементарных дизъюнкций

2.в каждой дизъюнкции нет одинаковых пропозициональных переменных (при этом в них есть каждая из пропозиций букв КНФ)

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

Теорема о приведении к СКНФ: любая тождественно истинная формула может быть приведена к СКНФ

Алгоритм приведения к СКНФ:

1 способ: строим таблицу истины и ищем строки с нулями

2 способ: строим КНФ и к каждой дизъюнкции добавляем нужный элемент

Билет 19

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

1. Дано множество формул: F₁,…,F_n, формула G является логическим следствием, если всякий раз, когда F₁=…=F_n=1 имеет место G=1

F₁,…, F_n=>G

F₁F₂...F_n G

Проверка, что формула является логическим следствием.

1 способ: Найти все наборы (x₁, …,x_k), для которых все F_i(x₁, …,x_k)=1 и (i=1…k), и проверить, что для них G(x₁, …,x_k)=1, если это так, то G – логическое следствие

2 способ: Найти все наборы, для которых G=0, если среди них найдётся (x’₁, …,x’_k), такой что все F_i(x’₁, …,x’_k)=1, тогда G не является логическим следствием, в противном случае- является

Билет 20

Карта Карно — графический способ минимизации логический функций, обеспечивающий относительную простоту работы с большими выражениями и устранение потенциальных повторных вхождений. Представляет собой операции попарного неполного склеивания и элементарного поглощения. Карты Карно рассматриваются как перестроенная соответствующим образом таблица истинности функции. Карты Карно можно рассматривать как определенную плоскую развертку n-мерного булева куба.
Карты Карно - один из способов минимизации как ДНФ, так и КНФ, помимо Карт Карно минимизировать (т.е. исключить повторные вхождения) ДНФ можно путем элементарных преобразований, а так же путем построения таблицы истинности.
p.s. обводить стоит количество единиц равное степени двойки и стараться захватить как можно больше (1, 2, 4, 8, 16) Захватывать можно и по краям сбоку в случае трех переменных и вообще по краям в случае 4х

 

Билет 21

Пусть M – непустое множество, местным предикатом на М называется выражение f(x­₁,..,x_n), которое при подстановке вместо x_i­ значения из М превращается в высказывание.

Местность предиката – кол-во свободных переменных, от которых он зависит. Пусть n – кол-во переменных в выражении, m – кол-во кванторов, тогда n-m – местность предиката.

Пусть u(x₁,..,x_n) и v(x₁,..,x_n) – предикаты на М, тогда предикат w(x₁,..,x_n) = u(x₁,..,x_n) * v(x₁,..,x_n) называется конъюнкцией или дизъюнкцией в зависимости от *

- квантор существования, высказывание – логическая операция, имеющая значение истина, если высказывание A(x) истинно хотя бы для 1 элемента , в противном случае ложна

– квантор единственности, высказывание – логическая операция, имеющая значение «истина», если на Х существует х для которого А(х) истинно, такой элемент один

Операция навешивания кванторов: пусть – предикат, предикат означает, что при является истиной

Билет 22

Назовем элементы множества М термами

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

Переменная называется связанной, если она входит в зону действия какого-либо квантора, в ином случае она свободна

Пример: ; x и y — связанные, а z — свободная

Вынос за скобки через конъюнкцию:

Док-во: пусть

Пусть теперь ###

Вынос за скобки через дизъюнкцию:

Док-во:

Пусть теперь ###

НЕЛЬЗЯ: выносить

Пусть A(x) – любое нечетное число, а B(x) – x – четное число, то B и A определены на

Тогда

А вот ###

НЕЛЬЗЯ: выносить

Пусть

Тогда

Но вот (x не может быть одновременно больше и меньше 2)

Билет

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

Как меняются кванторы при отрицании:

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

Для разноименных кванторов () изменение порядка может привести к изменению истинности

 

Билет

ПНФ – предикатная формула вида: q₁x₁...q_nx_n F(x₁,..,x_n), где q_i – кванторы, x_i – связанные переменные, а F – предикат

Для любой формулы логики первого порядка существует равносильная ПНФ

Алгоритм: пусть дана формула F(x₁,..,x_n)

1.Избавимся от эквивалентности и импликаций

2.Заносим отрицание к переменным

3.Переименовываем переменные, принадлежащие к разным кванторам и те переменные, под квантором которых обозначено единство с глобальными переменными

4.Выносим кванторы вперед …. PROFIT!

Билет 25

Принцип перемножения:Согласно ему, если элемент A можно выбрать n способами, и при любом выборе A элемент B можно выбрать m способами, то пару (A, B) можно выбрать n·m способами.
Пример: Выбрать книгу И диск из 10 книг и 12 дисков можно 10*12=120 способами.
Размещения с повторениями: Если есть множество из n типов элементов, и нужно на каждом из m мест расположить элемент какого-либо типа (типы элементов могут совпадать на разных местах), то количество вариантов этого будет n в степени m.
Вывод формулы: Метод мат. индукции.
При k=1 теорема верна, так как сами элементы a(1) - a(n) составляют всевозможные размещения элементов по одному, то число этих размещений равно n=n^1.
Предположим, что число размещений с повторениями из n элементов по k равно n^k. Составим из данных n элементов всевозможные размещения с повторениями по k+1 элементу. Во всяком размещении с повторениями по k+1 элементу a(1) - а(k+1) первые k элементов a(1) - а(k) образуют некоторое размещение с повторениями из n по k элементов. В качестве последнего k+1-го элемента может быть взят любой из n элементов. При различных выборах a(k+1) получаются различные размещения. Кроме того, два различные размещения k-го порядка дают два различные размещения k+1-го порядка.
Таким образом, число всех размещений k+1-го порядка равно (n^k)*n=n^(k+1).
Размещения без повторений: Пусть задано некоторое конечное множество из n элементов. Пусть из числа его элементов выбраны k различных штук (k ≤ n), тогда говорят, что произведена выборка объёма k. Если важен порядок, в котором произведена выборка элементов, то это называется размещением из k элементов по n.
Для размещения без повторения справедлива формула А из n по k = n!/(n-k)!
Доказательство: первый элемент можно выбрать n различными способами, второй – (n – 1) способом, третий – (n – 2) способами, а k-й – (n – k + 1) способом.
Формула размещений - это перемножение всех этих скобок.
Перестановка - это размещение n элементов на n местах.
Количество перестановок равно A из n по n = n!
Док-во: 1 элемент можно выбрать n различными способами, 2 – (n – 1) способами,... n-й – единственным способом. Таким образом, при перемножении кол-ва способов получаем n!

 

Билет

Сочетанием без повторений называется такое размещение, при котором порядок следования элементов не имеет значения. (Если множество А состоит из m элементов, то его подмножества, содержащие k элементов, называются сочетаниями без повторений из m элементов по k элементов.)

Всякое подмножество X состоящее из m элементов, называется сочетанием из n элементов по m.

Таким образом, количество вариантов при сочетании будет меньше количества размещений.

Число сочетаний из n элементов по m обозначается

Формула

Число сочетаний без повторений обладает следующими свойствами:

Билет 27

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

1. = 2. 3. — рекурентность

Док-во п.3:

###

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

Бином Ньютона:

Видно, что в этом многочлене будут x­ⁿ и yⁿ

повторяются n раз

Получить комбинацию можно n способами

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

 

Билет 28

Всякое размещение с повторениями, в котором элемент а₁ повторяется к₁ раз, элемент а₂ повторяется к₂ раз и т.д. элемент а_n – к_n раз называется перестановкой с повторениями порядка n где k₁+k₂+..+k_n в которой элементы a₁,…,a_n повторяются k₁+..+k_n соответственно раз

Док-во: если будем считать все k₁+..+k_n элементов перестановки с повторениями различными, то всего различных вариантов перестановок k₁+..+k_n элементов (k₁+..+k_n)!, но все элементы а можно переставлять друг с другом, точно так же можно переставлять и a₁,…,a_n => всякая перестановка может быть записана k₁!k₂!..k_n! способами => число различных перестановок с повторениями =

Коэф при x^a1y^a2z^a3=

-

Пусть S={s₁,s₂,..,s_n}, Если , то характеристическим вектором подмножества является двоичная строка вида (b₁, b₂,.., b_n), где

Теорема: Число подмножеств конечного множества, состоящего из n элементов = 2ⁿ

Док-во: допустим у нас имеется множество из n эл. При составлении подмножеств первый элемент может принадлежать или не принадлежать подмножеству, т.е. первый элемент можно выбрать двумя способами; по правилу умножения получаем 2*2*2*…=2ⁿ

Билет 30

Пусть дано X={x₁,x₂,..,x_n}; Сочетанием с повторениями из t элементов называется любой набор из t объектов Х, при этом может входить в набор более 1 раза

Характеристическим вектором мультимножества А называется последовательность Ã=(a₁,a₂,..,a_n), где a_i – число вхождений x_i в А =>

Число сочетаний с повторениями:

Будем строить k -элементные сочетания с повторением из А={а_1, а_2, …, а_n}. В каждом таком наборе сначала расположим элементы типа а₁, потом типа а₂ и так далее. Каждому k -сочетанию с повторениями поставим в соответствие последовательность из нулей и единиц длины n+k=1. Число единиц в этой последовательности равно k, а число нулей равно n-1. Каждый 0 отделяет набор типа а_i от набора а_i+1 в данном k -сочетании с повторениями. В частности, если 0 стоит на первом месте, то это означает, что элементов типа а₁, в данном k -сочетаний нет; если нет элементов типа а_i, то между единицами, соответствующими элементам типа а_i-1 и а_i+1 стоит два нуля. (проиллюстрируем эту конструкцию: пусть А= {а₁, а₂, а₃, а₄}; 6-сочетанию [а₁, а₁, а₂, а₃, а₃, а₄] соответствует последовательность (1, 1, 0, 1, 0, 1, 1, 0, 1) <характеристический вектор вв. 0 и 1>. Каждое k -сочетание с повторением однозначно определяет указанную последовательность и наоборот. Число всех упорядоченных нулей и единиц последовательностей из нулей и единиц длины n, в которых присутствует l нулей, равно . Следовательно таких последовательностей ###