 |
Несчетные множества. Теорема Кантора.
|
|
|
|
Несчетное множество – это такое множество, элементам которого нельзя сопоставить элементы множестваN (отсутствует биекция между ним и множеством N). Пример: Множество всех точек отрезка [0;1].
Теорема Кантора. Между множеством всех точек отрезка [0;1] и множеством N нельзя установить биекцию – взаимно однозначное обозначение.
Доказательство:
Пусть $ j:N®[0;1]
1«a1=0,a11a12...
........
к«aк=0,aк1,aк2,...,где a1,…,aк точки отрезка [0;1].
bÎ[0;1]. b=0,В1,В2......Вк...., где Вi¹0, Bi¹aii.
У элемента b не будет прообраза Þ отображение будет не сюрънективно Þ не биекция. Получено противоречие. Теорема доказана.
Континуум. Равномощность множеств.
Мн-во, равномощное мн-ву точек отрезка [0,1] называется множеством мощности континуум. Между множеством с такой мощностью можно установить биекцию.
1) [a;b] ~ [c;d]
(a;b) ~ (c;d)
(x-a)/(b-c) = (y-c)/(d-c), y=kx-b. Таким образом установили биекцию.
2) [0;1]~(0;1)
Утверждение: Пусть А - бесконечное множество, В - конечное или счетное. Тогда (АÈВ)~A. Из бесконечного множества А выделим конечное А: А Í А. При этом условии справедливо А=(А\ А) È А. АUB=((А\ А)È А)ÈВ = (А\ А)È(А ÈВ)~(А\ А)È А =А, ч.т.д.
3) [0,1]~R, устанавливаем y=arctg x, тогда [-p/2; p/2] \ R, y=(1/p) arctg x + ½
Теорема Кантора-Вейерштрасса.
Пусть A и B произвольные множества A1ÍA, B1ÍB и при этом A~B1, B~A1
Тогда A~B. Есть 4 случая:
1) A~B1 и B~A1 è A~B
2) A~B1, не $ A1ÍA: A1~B
m(B)>m(A) m - мощность
3) B~A1, не $ B1ÍB: B1~A
m(A)>m(B)
4) Любые два множества всегда сравнимы по мощности между собой.
Частично упорядоченное множество называется вполне упорядоченным, если каждое его не пустое подмножество содержит наименьший элемент. Множество N является вполне упорядоченным. Если множества A и B вполне упорядочены, то их мощности сравнимы.
|
|
|
Теорема Цермело. Каждое множество может быть вполне упорядоченным.
Доказательство: Основано на аксиоме выбора, сформулированной Цермело.
Аксиома выбора: Пусть X – произвольное множество, тогда $ функция j, сопоставляющая любому не пустому подмножеству X:(AÍX, A¹Æ) некоторый элемент aÎA, j(A)=a, j - выбирающая функция.
Теорема о мощности множества всех подмножеств.
Теорема: м(Á(А))>м(А). Мощность множества всех подмножеств множества А больше мощности множества А. Для конечных множеств из м элементов: rm{a1,....,am}; rm > m. Доказательство: м(Á(А))³м(А); м(Á(А))¹м(А), т.е. нельзя установить биекцию между А и Á(А). Предположим обратное. Пусть а1«А1, а2«А2,....; а1,а2ÎА; А1, А2ÎÁ(А). Сформулируем мн-во Х, у которого нет прообраза, следующим образом: если а \® А и
а Î А, Þ а ÏХ. Если а «А и а ÏА Þ а ÎХ. Покажем, что не существует х«Х, если
«X и хÎХ, то x ÏХ и наоборот. Þ card(Á(N))=cont.
Равносильность формул логики высказываний
Для любых формул A, B, C справедливы следующие равноситльности.
1) AVB=BVA 1)` A&B=B&A - коммутативность
2) A&A=A 2)` AVA=A - идемпотентность
3) A&(B&C)=(A&B)&C – ассоциативность с &
4) AV(BVC)=(AVB)VC – ассоциативность с V
5) AV(B&V)=(AVB)&(AVC) – дистрибутивность V относительно &
6) A&(BVC)=(A&B)V(A&C) – дистрибутивность & относительно V
7) A&(AVB)=A - первый закон поглощения
8) AV(A&B)=A – второй закон поглощения
9) ØØA=A – снятие двойного отрицания
10) Ø(A&B)= ØAVØB – первый закон Де Моргана
11) Ø(AVB)= ØA&ØB – второй закон Де Моргана
12) A=(A&B)V(A&ØB) – первая формула расщепления
13) A=(AVB)&(AVØB) – вторая формула расщепления
Любая равносильность может быть легко доказана с помощью таблицы истинности. Следующая группа равносильностей показывает, что одни связки могут выражены другими.
14) A~B=(AÉB)&(BÉA)=(A&B)V(ØA&ØB)
|
|
|
15) AÉB=ØAVB=Ø(A&ØB)
16) AVB=ØAÉB=Ø(ØA&ØB)= Ø(ØA&ØB)
17) A&B=Ø(AÉØB)= Ø(ØAVØB)
Пусть A=B и C – произвольная формула. Тогда ØA=ØB, A&C=B&C, C&A=C&B, AVC=BVC, CVA=CVB, AÉC=BÉC, CÉA=CÉB, A~C=B~C, C~A=C~B.
18. Закон двойственности логики высказываний.
Если АºВ, то А*ºВ*. Пусть АºВ. Если <xi1,....,xik> - список переменных, от которых зависят формулы А и В (и, очевидно, А*, В*), а <t1,....,tk>- оценка этого списка, то А* принимает значение (истина) на этой оценке в том и только в том случае, если (А*)* (т.е. А) принимает значение (ложь) на оценке <s1,...,sk>, двойственной оценке <t1,...,tk>, но последнее в силу равносильности А и В имеет место Û В принимает значение (ложь) на оценке <s1,...,sk>. С другой стороны, В* принимает значение (истина) на оценке <t1,....,tk> только тогда, когда (В*)* (т.е. В) принимает значение (ложь) на <s1,...,sk>. Итак, видим, что истинность А* на <t1,...,tk> равносильна истинности В* на <t1,...,tk>. Поскольку оценка <t1,...,tk> произвольна, получаем, что А*ºВ*. Закон двойственности можно применять для нахождения новых равносильностей.
ДНФ и КНФ
ДНФ
Формула находиться в ДНФ, если она является дизъюнкцией элементарных конъюнкций.
ДНФ определяется неоднозначно.
Теорема: Для любой формулы A можно указать равносильную ей формулу B, которая находится в ДНФ. Доказательство:
1) Строим A1=A и представляет A1 с использованием только &, V, Ø.
CÉB=ØCVB=Ø(A&ØB)
C+D=Ø(A~B)
C~D=(C&D)V(ØC&ØD)= (ØAVB)&(AVØB)
2) Сделаем так, чтобы все отрицания стояли перед переменными, а не перед скобками.
Если A1=C&D
Если A1=CVD
Если A1=ØØC=C
Если A1=Ø (CVD) =ØC&ØD
Если A1=Ø (&D) =ØCVØ
3) Применяя Обобщенную дистрибутивность конъюнкции, преобразуем формулу.
A1=A, и A1 – представлена в виде ДНФ.
Пример:
(Øx1~x2) Éx2=Ø(Øx1~x3)Vx2=Ø((x1Vx3)&(Øx3VØx1))Vx2=
=Ø((x1Vx3)VØ(Øx3Vx1)Vx2)=(Øx1&Øx3)V(x3Vx1)Vx3
КНФ
КНФ – конъюнкция элементарных дизъюнкций. (x1VØx2)&x2&(Øx1Vx2Vx3)
Если A находится в ДНФ, то двойственная ей функция в КНФ. КНФ определяется неоднозначно.
Теорема: Любую формулу можно привести к КНФ.
Доказательство: Аналогично доказательству по приведению к ДНФ.
|
|
|
СКНФ СДНФ
Сокращенная ДНФ:
В отличие от ДНФ и КНФ определяется однозначно. Пусть формула A зависит от списка переменных <x1, …, xn>. Говорят, что A находиться в СДНФ относительно этого списка переменных, если выполняется три условия:
1) A находиться в ДНФ
2) Каждый дизъюнктивный член является n-мерной конъюнкцией.
3) Все дизъюнктивные члены попарно различны.
Пример: (x1&Øx2&x3)V(x1&x2&x3) – СДНФ.
Пример: (x1&Øx2)V(x1&x2) – не СДНФ, нет x3 или Øx3.
Теорема о приведении формулы к СДНФ:
Пусть A зависит от списка переменных <x1, …, xn> и A не тождественно ложно. Тогда существует B=A, такое, что B находиться в СДНФ форме. Доказательство:
1) B=A, A - в ДНФ.
2) Если в B есть конъюнкция, содержащая xi и Øxi, то вся эта конъюнкция является ложью и вычеркивается, и но по условию в B есть другие конъюнкции не являющиеся тождественной ложью.
3) Вычеркиваются все повторения конъюнкций.
4) Проверяем, что в каждой конъюнкции xi или Øxi встречается не более одного раза. Если нет, то xi & xi = xi, и Øxi & Øxi = Øxi.
5) Если в скобке только две составляющие, то по закону расщепления добавить третью.
6) Расставить символы в конъюнкции в порядке следования по алфавиту.
Теорема о единственности СДНФ:
Если B1 и B2 – формулы в СДНФ относительно списка переменных <x1, …, xn> формулы A, то B1 и B2 могут отличаться только порядком своих дизъюнктивных членов. Если A и B имеют одну СДНФ, то A=B.
Сокращенная КНФ:
Формула A находиться в СКНФ, если:
1) А находится в КНФ
2) B – конъюнкция элементарных дизъюнкций.
3) Элементы дизъюнкции попарно различны.
Теорема о приведении формулы к СКНФ:
Пусть A зависит от списка переменных <x1, …, xn> и A не тождественно ложно. Тогда существует B=A, такое, что находиться в СКНФ форме. Доказательство:
1) B=A, A - в ДНФ.
2) Если в B есть дизъюнкция, содержащая xi и Øxi, то вся эта дизъюнкция является истиной и вычеркивается, по условию в B есть другие дизъюнкции не являющиеся тождественной истиной.
3) Вычеркиваются все повторения дизъюнкции.
4) Проверяем, что в каждой дизъюнкции xi или Øxi встречается не более одного раза. Если нет, то xi & xi = xi, и Øxi & Øxi = Øxi.
|
|
|
5) Если в скобке только две составляющие, то по закону C=(CVx)&(CVØx) добавить третью.
6) Расставить символы в дизъюнкции в порядке следования по алфавиту.
21. Тождественно истинные формулы логики высказываний. Проблемы и решения разрешимости логики высказываний.
Пусть формула A зависит от списка переменных <xi1, …, xik>. Формула A называется тавтологией (тождественно истинной формулой), если на любых оценках списка переменных <xi1, …, xik> она принимает значение истины. Формула A называется тождественно ложной, если на любых оценках списка переменных <xi1, …, xik> она принимает значение лжи. Формула A называется выполнимой, если на некоторой оценке списка переменных <xi1, …, xik>она принимает значение истины. Формула A называется опровержимой, если на некоторой оценке списка переменных <xi1, …, xik> она принимает значение лож. Как и в определении равносильности, здесь не имеет значения, будут ли в списке фиктивные переменные.
Приведем утверждения, которые являются очевидными следствиями данных определений:
1) A- тавтология тогда и только тогда, когда A не является опровержимой.
2) A- тождественно ложна тогда и только тогда, когда A является выполнимой.
3) A - тавтология тогда и только тогда, когда ØA тождественно ложна.
4) A – тождественно ложна тогда и только тогда, когда A тавтология.
5) A~B - тавтология тогда и только тогда, когда A и B равномощны.
С точки зрения тавтологии суть не что иное, как логические законы, ибо при любой подстановки вместо переменных в результате получим истинное высказывание.
Перечислим наиболее важные тавтологии. A, B, C – произвольные формулы.
1) AVØA
2) AÉA
3) AÉ (BÉA)
4) (AÉB) É((BÉC) É(AÉC))
5) (AÉ(BÉC)) É((AÉC) É(AÉC))
6) (A&B) ÉA, (A&B) ÉC
7) AÉ(AVB), BÉ(AVB)
8) AÉ(BÉ(A&B))
9) (ØAÉØB) É((ØBÉA) ÉB)
10) ((AÉB) ÉA) ÉA {закон Пирса}
Каждую из тавтологий можно обосновать, например, составить таблицу истинности и вычислить по ней значение A, B, C.
При доказательстве утверждений различных математических теорий обычно используют рассуждения, которые на языке логики модно выразить формулами.
Проблемой разрешимости для логики высказываний является проблема: есть ли такой алгоритм действий, чтобы за конечное количество шагов определить, является ли формула тавтологией? Она разрешима, так как всегда можно перебрать все оценки списка переменных и вычислить все значения формулы.
22. Правильные рассуждения. Примеры. Косвенный метод доказательства.
|
|
|
Рассуждение называется привильным, если из конъюкции посылок следует заключение, т.е. всякий раз, когда все посылки истинны, заключение тоже истинно. Пусть P1..Pn – посылки, D- заключение. Тогда для правильности рассуждения по схеме (P1…Pn)/D, т.е. утверждения о том, что из данных посылок P1,…,Pn следует заключение D, требуется установить тождественную истинность формулы (P1&…&Pn)ÉD*. * - вообще говоря выражение (P1&…&Pn)ÉD не удовлетворяет определению формулы. Однако далее мы убедимся, что такая запись корректна. Т.к. речь идет лишь о правильности руссуждения, истинность заключения не является ни необходимым, ни достаточным условием правильности рассуждения.
Рассмотрим два рассуждения.
1. Если число 5 простое, то оно нечетное. Число 5 нечетное, следовательно, число 5 простое. Это рассуждение по схеме (AÉB,B)/A. Легко проверить, что формула ((AÉB)&B)ÉA не является тождественно истинной.
2. Если Петр занимается спортом, то Петр никогда не болеет. Петр занимается спортом. Следовательно, Петр никогда не болеет. Это рассуждение по схеме (АÉВ,А)/В. Формула ((АÉВ)&A)ÉB тождественно истинна, и, значит, рассуждение правильно.
Распространенными схемами правильных рассуждений являются следующие схемы (АÉВ,А)/В и (AÉB,ØB)/ØA. Рассмотрим условное высказывание вида АÉВ, где А – конъюкция посылок, В-заключение. Иногда удобнее вместо док-ва истинности этого условного высказывания установить логическую истинность некоторого другого высказывания, равносильного исходному. Такие формы доказательства называются косвенным методом доказательство. Одним из них является способ доказательства от противного. Предположим, что утверждение АÉВ ложно. Тогда, исходя из этого предположения, приходим к противоречию, т.е. доказываем, что некоторое утверждение (соответствующее высказыванию С) выполняется и не выполняется (одновременно). Применимость этой формы косвенного метода доказательства оправдывается равносильностью.
АÉВºØ(АÉВ)É(С&ØC)º(A&ØB)É(C&ØC).
Существуют и другие схемы доказательства от противного.
AÉBº(A&ØB)ÉØA
AÉBº(A&ØB)ÉB
Еще одной формой косвенного метода доказательства является доказательство по закону контрапозиции, основанное на равносильности AÉBºØBÉØA, когда вместо истинности АÉВ мы доказываем истинность ØBÉØA.
|
|
|
