Файл: Войтишек В.В. Курс лекций по математике для слушателей подготовительного отделения.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 08.07.2024
Просмотров: 126
Скачиваний: 1
Третий припер. Во множестве действительных чисел истинно |
|
|||||||||
высказывание |
(Ѵх)(Ѵу) [ ( х * ц ) Ѵ |
( х = у ) ѵ |
( х > у ) ] , |
|
которое |
|||||
равносильно |
такому высказыванию |
|
|
|
|
|
||||
|
( Ѵ х ) ( Ѵ у ) [ |
ÉZ-sy; |
=* (CX=lj) |
У (X>(j))] ■ |
■ |
|
||||
Обоснование |
этого |
утверждения: |
|
|
|
|
|
|
||
Известно, что импликацию |
А |
|
ß |
можно заменить |
сложным вы |
|||||
сказыванием |
Д у б , |
. и |
еолн |
есть высказывание |
с , |
то (с) |
С*$ |
|||
I<я>'С (по определению связки |
"отрицание"). |
|
|
|
|
|||||
Значит, |
высказывание |
|
|
|
|
|
|
|
||
(Ѵл)(Ѵу) [ ( х * у ) |
|
( ( x = y ) v |
( x>y»J |
<#=> |
|
|
||||
(ѴхХУф [ ( x c y ) |
и |
(x=y ) |
V |
(x>y)] |
|
|
|
|||
(Vx)Qfij)[CX<ip |
У |
(X=tj) |
V |
(x>y)]. |
|
|
|
|||
Определение. Набор символов (За:) Р(х) |
переводится так: "суще |
|||||||||
ствует элемент х |
в области |
определения |
Р (х ) , |
обладающий свой |
||||||
ством Р ( х ) ! |
|
|
|
|
|
|
|
|
|
|
Замечание. Квантор всеобщности У |
есть обобщение конъюнкции |
|||||||||
на бесконечную область определения дяя предиката. Квантор сущест
вования |
обобщает дизъюнкцию. |
Действительно, пусть |
х е { о . па£,...1 |
||||
а }, , |
другими словами, л |
принимает конечное |
число |
значений. |
|||
Тогда мы можем сказать, что |
P ( a t ) истинно или ложно, |
если под |
|||||
ставим |
х=й^ |
в предикат. Но тогда равносильны высказывания |
|||||
|
с ѵх)Р(х) |
<=> Р с а ) л р с а л) л р с а 3) а ... |
л Р(ая) |
|
|
||
и |
(Зх)Р(х) |
*=> РСа,) ѵР (а £ )ѵРСа3) у ... |
v P c a j . |
|
|||
Отсюда становятся яснее законы (правила), связывающие высказыва ния с кванторами и их отрицания;
(Ух)PCX) |
-«=> |
( J x ) P ( x ) , , |
(З х ) Р (х ) |
•*=*■ |
(ѵх)-Р(х) . |
Эти два правила аналогичны правилам (законам де Моргана) для ло гических связок:
(Алб) *=* (Д ѵВ) ;
(АуВ) +* (ЙAß) .
41
Истинность приведённых высказываний можно проверить, подставляя
в левую и правую части высказывания всевозможные пары, |
сделанные |
|||
из двух символов: 0 и I . |
|
|
|
|
§ 4 . Законы математической логики |
|
|||
Интересными законами для логических овязок л , ѵ |
являются |
|||
такие: |
|
|
|
|
( О л В ) ѵ С |
<=*■ |
( й ѵ С ) |
л ( В ѵ О ; |
|
( А уВ ) л С |
^ |
(ЙЛС) |
V (ВАС). |
|
Их справедливость можно проверить, подставляя восемь возможных
наборов нулей и единиц для трех высказываний Я, 3 ,С в левую
и правую части. Результат подстановки |
записывают в виде 'таблицы. |
|||||
й |
В |
С |
(ЙЛВ)ѴС |
ЙѵС |
ВѴС |
(ЙѴС)А (ВѵС) |
о |
0 |
0 |
о |
0 |
0■ |
0 |
о |
о |
L |
L |
1 |
L |
і |
о |
L |
0 |
0 |
0 |
1 |
0 |
о |
1 |
і |
1 |
1 |
i |
і |
1 |
О |
о |
0 |
{ |
О |
о |
1 |
О- |
1 |
1 |
L |
1 |
і |
1 |
і |
о |
1 |
1 |
1 |
і |
1 |
1 |
1 |
1 |
L |
1 |
1 |
1 |
г |
3 |
4 |
5 |
6 |
7 |
Сравнение столбца * 4 и столбца J6 7 подтверждают, что (Дл8)ѵс*+ |
|
сЙѴС)А (ВѴС): |
|
Аналогичные законы верны для высказываний с кванторами |
|
((Ѵя)Р(Х)) а (( Ух) Q (X)) |
(Ѵх) ( P ( X ) A Q(X)) , |
( О х )Р(х)) у ((Зх) Q (X)) <=* ( З х ) ( Р ( х ) V Q ex)).
Дадим сводку правил для сложных высказываний с употреблением
связок л , V и отрицания. |
|
|
( й Л В) ѴС .<^ |
( в ѴС) Л (В ѴС) ; |
|
( й ѵ&) АС |
|
СйлС) ѵ ( В а с) ; |
( й л в ) |
<=? |
й ѵ В ; |
(йѵЗ) |
< = $ . д л Ъ ; |
|
42
( Д л В ) л С |
-«=>■ |
fl А (В AC) |
І |
|
|
||||
( f l y В ) |
у с . |
■*=*■ |
fl |
v ( ß v C ) |
; |
|
|
||
fl |
|
A B |
■*=* |
в л |
fl |
|
|
|
|
■fl |
|
vB |
<=* |
B v f l ; |
|
|
|
|
|
ДЛД |
<=> fl; |
|
f l v f l < ^ f l ; |
flfifl |
4=^0,- |
|
|||
flvfl |
^ |
I |
(закон исключённого третьего) і |
||||||
: l v f l < * ? i ; |
|
1лА < ^> Д ; |
( Ъ ^ |
fl,; |
|
||||
Т <*> |
О |
; |
|
ОУ fl |
fl; |
0 а А<£=?0 ; |
U ^ I. |
||
Заметим, что не все математики безраздельно принимают эти закона и умеют строить логические системы, в которнх закон исключённого третьего не выполняется (см. Р. Линдон, Заметки по логике, стр.
52).
I5, Примеры
Взаключение приведём некоторые примера приложения математик ческой логики к алгебре, геометрии и к схеме двоичного сумматора.
Алгебра. |
Пример I. ' |
. |
* |
Данн: 1. |
Высказьшательная форма х - 6 х + 8 . |
||
2. |
Уравнение (логическая функция) х 2 - 6 х + 8 = о . |
|
|
3.Неравенство (логическая функция) Xе"- 6 x t 8 >о.
4.Неравенство (логическая функция) х 2 - б х +8-<0.
Здесь |
х е [I,£3.4, 5} . Значения функций' зашием в виде таб-> |
||||
лигш |
х 2- 6 х +8 |
х?-6х+8=о |
Х 2-6х+8Ю |
X 2- б х +8*0 |
|
X |
|||||
1 |
|
3 |
0 |
і |
0 |
£ |
. |
0 |
1 |
о |
о ■ |
3 |
-1 |
0 |
о |
1 |
|
ч |
|
0 |
1 |
о |
0 |
6 |
|
3 |
0 |
1 |
0 |
В. первом и втором столбцах числа используются как обычно. В треті^ ем, четвертом и пятом столбцах нуль означает ложность высказыва ния при данном X , единица - истинность того же высказывания.
43
Пример 2 . Решить неравенство |
/х) + /х-£І |
Подразумевается, что х е £ , где Л |
означает множество действи |
тельных чисел. |
|
0x1 + lx-£l>V) <=» |
J ^ |
\
(СХ^О)Л(-Х-Хі-£>У))ѵ (СХуО)Л (Х<&)Л (Х+&-Х>Ч)) V
Ѵ(СХ7/2)Л (Х+Х-& >4)) ■*=*
ссх^0)л Сх<-П) у ССх>0) Л(Х*&)Л0) Y ( ( x > 2 ) л сх>з))
|
|
(Х<-1) У ОѴ СХ>5) ^ |
(х < - 1 ) V (Х>5). |
|
|
|
|||||||
Множество решений неравенства |
|
|
|
|
|
|
|
|
|||||
|
|
|
U - { ѴХ':СХС-П у |
( х > 3 ) } - |
|
|
|
|
|||||
|
Пример 3 . Если мы имеем |
теорему, |
то её |
можно всегда предста |
|||||||||
вить в виде |
я =*ß . |
|
|
|
|
|
|
|
|
|
|
||
|
Иногда |
её доказывают методом от противного. За посылку берут |
|||||||||||
Ъ |
и доказывают, |
что |
Ъ = * Я . |
По таблице истинности |
можно убедить |
||||||||
ся в правильности |
высказывания. |
|
|
|
|
|
|
|
|||||
|
|
|
|
Сй ^ ß ) ■-*—^ ( В ^ й ) - |
|
|
|
|
|
||||
|
Используем этот факт для доказательства теоремы стереометрии. |
||||||||||||
Плоскости обозначим буквами |
|
, f |
То, |
что |
плоскости j |
и |
|||||||
6 |
пересекаются, |
обозначим так: |
с f x â ) . |
То, |
что плоскости |
(3 |
|||||||
и 6 |
параллельны, |
запишем |
так: |
( 5 і&) . |
|
|
|
|
|
||||
|
ТЕОРЕМА |
(признак |
параллельности двух плоскостей). |
|
|||||||||
|
|
|
(Vp[(fXaL) |
=> |
|
( a u f ) . |
|
|
|||||
(Если произвольная плоскость |
[ |
пересекается |
с данной |
плоскостью |
|||||||||
оі |
и иэвестно, что та же |
плоскость j |
пересекается |
с другой |
|
||||||||
данной плоскостью |
/5 |
, то |
данные |
плоскости |
ы. |
и |
В |
параллельны). |
|||||
|
ДОКАЗАТЕЛЬСТВО. |
' |
|
|
|
|
|
|
7 |
|
|
||
Условие |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
((Vf) I QXoC) => Cp/S)] => (oi-lji)) |
|
|
' |
|
|
||||||
|
( CcLU/b) => ( V p [ |
|
|
=•=*■ (p/ä)]) ^=3- |
|
|
|
||||||
|
((ы-xjè) => |
(3jf)[ Cjfxoc) |
=*■ q x p i ) |
<*=>• |
|
|
|
||||||
44
((■=1x/b) => (3 f)[([x o l) V( j f x . ß) ] ) <s=?
(СЫ-xß ) => (3f) [ (Jxöc.) Л (/xjS>)D <=$
((dx/b) =S> (3/) [ ( /x d ) A (/Hjb)]).
іПоследнее высказывание справа значит, что достаточно |
провести |
||||
плоскость j |
|
через точку, |
лежащую на плоскости |
ы. , |
параллельно |
плоскости |
(Ь. |
Последнее |
всегда можно сделать, |
если |
плоскости |
d и уб пересекаются. |
|
|
|
||
Замечание. Правила построения отрицательного высказывания с |
|||||
кванторами |
показывают также справедливость нашего замечания, что |
||||
для опровержения какого-нибудь утверждения достаточно привести один пример, когда предполагаемое правильным свойство не выпол няется. В нашем примере на стр. 34 есть четырехугольник, у которо го диагонали взаимно-перпендикулярны, но этот четырехугольник не ромб.
Пример 4 . Двоичный сумматор.
Конструкторы цифровых машин стремятся, чтобы можно было сооб
щить машине условия задачи.так-же, как мы их сообщаем собеседнику или преподавателю, и чтобы машина отвечала как грамотный собесед ник. Так что в недалёком будущем нам (если мы не конструируем ма
шины) достаточно воспринимать машину как"чёрный ящик"(ящик, закры
тый и запечатанный, внутренности этого ящика нам не доступны или, точнее, нас совсем не интересуют). Если же вскрыть цифровую машину,
то мы обнаружим в ней несколько чёрных ящиков, соединенных между собой (их названия: устройство ввода, устройство вывода, запоминаю
щее устройство, устройство управления, арифмометр). Чтобы понять, * как складывает машина, нам придётся вскрыть арифмометр. Мы обнару жим два регистра (на каждом запоминается одно из слагаемых) и
сумматор. |
1 |
|
|
|
|
|
Сумматор можно считать тоже "чёрным |
ящиком? в который посту |
|||||
пает три |
сигнала; й |
- значение цифры (двоичной цифры по предполо |
||||
жению) данного разряда первого слагаемого, |
В - |
значение двоичной |
||||
цифры соответствующего |
разряда второго слагаемого и |
г |
-единица |
|||
переноса из младшего |
разряда. |
|
|
|
|
|
На выходе сумматора должны быть два сигнала: |
3 |
- |
значение |
|||
суммы в данном разряде |
и & - единица переноса в |
следующий разряд. |
||||
45