Как найти число при котором истинно высказывание

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

Алгебра высказываний

Под высказыванием понимаем всякое утверждение (повествовательное предложение), про которое всегда определенно и объективно можно сказать, является оно истинным или ложным. Например, «5-3 = 2» или «В неделе семь дней» — истинные высказывания, а «5 > 8» или «В русском языке 35 букв» — ложные высказывания. Синонимами слова «высказывания» можно считать: логическое высказывание, булевское выражение, суждение, утверждение и т.п. Фразы: «Ура!», «Который час?» — не являются высказываниями.

Если высказывание истинное, то ему предписывается значение «истина» (другие обозначения: «1», «ДА» , «И», «+», «true»). Ложному высказыванию предписывается значение «ложь» (другие обозначения: «О», «НЕТ», «Л», «-«, «false»). Совокупность возможных значений высказывания образует множество истинности {0,1} и {И,Л}.

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

Логические операции

Операции над высказываниями задают в виде таблиц, называемых таблицами истинности.

Отрицание высказывания

Для каждого высказывания А может быть сформировано новое высказывание отрицание высказывания А, которое истинно, когда А ложно, и ложно, когда А истинно. Символ соответствует логическому союзу «не». читается «не А» или «не верно, что А». Отрицание — одноместная (или унарная) операция. Последующие операции — двухместные (или бинарные). Например, если истинное высказывание, то ложное высказывание (отрицание А), или если в комнате холодно», в комнате не холодно». Отметим, что высказывание «в комнате жарко» не является отрицанием В.

Конъюнкция высказываний

Конъюнкцией высказываний А и В называется высказывание которое истинно только в том случае, когда и А, и В одновременно истинны. Выражение читается «А и В». Пример: пусть делится на делится на 4″. Тогда формула имеет смысл: «12 делится на 3 и на 4».

Операцию конъюнкции можно определить и для нескольких высказываний как связку высказываний, объединенных союзом «и». Конъюнкция из п высказываний — новое высказывание, причем высказывание

имеет значение «истина», если истинны. Во всех других случаях эта конъюнкция имеет значение «ложь». Пусть, например, отец старше сына Мурманск севернее Смоленска». Тогда высказывание («8=3 и отец старше сына, и

Мурманск севернее Смоленска») — ложное высказывание. В то время как и отец старше сына, и Мурманск севернее Смоленска» — истинное высказывание.

Дизъюнкция высказываний

Дизъюнкцией высказываний А и В называется высказывание которое ложно только тогда, когда и А, и В ложны одновременно. Дизъюнкция имеет значение «истина», если хотя бы одно из высказываний, входящее в дизъюнкцию, является истинным. Выражение читается «А или В». Пусть Тогда

Операцию дизъюнкции можно определить для нескольких высказываний как связку высказываний, объединенных союзом «или»,

В этом случае высказывание А истинно, если истинно хотя бы одно из высказываний, входящих в связку.

Импликация высказываний

Импликацией высказываний А и В называется высказывание которое ложно только в том случае, когда А — истинно, а В — ложно. Во всех других случаях импликация имеет значение «истина». Символ соответствует логическому союзу: «если А, то В». Например, А — «целое число делится на 4, то оно делится на 2». Для иллюстрации содержательного смысла импликации рассмотрим следующий пример: А «папа завтра получит премию», В «папа завтра купит сыну велосипед». Тогда импликация может быть сформулирована так: «если папа завтра получит премию, то купит сыну велосипед».

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

Эквивалентность высказываний

Эквивалентностью высказываний А и В называется высказывание которое истинно, когда высказывания и А, и В оба истинны или оба. ложны. Символ логической эквивалентности соответствует связке «тогда и только тогда». Пример. Пусть А «число З является четным», В «число является четным». Высказывание «число З является четным тогда и только тогда, когда -четное число» есть эквивалентность высказываний А и В. Эквивалентность высказываний может быть задана следующей таблицей истинности:

Замечание. Характерной особенностью операций над высказываниями является введение логических союзов с точно определенным смыслом, не допускающим никакой двусмысленности в толковании этих символов. Таким образом, математическая логика применима не для любых высказываний, а только для таких, которые допуск кают четкую оценку в двоичной системе «истина — ложь». Для преодоления такого рода ограничений в рамках нечеткой математики разрабатывается нечеткая логика.

Если в выражении встречаются различные логические операции, то в качестве естественного порядка (выполняемого поочередно слева направо) используется следующая последовательность: Это означает, что сначала выполняются операции отрицания, затем конъюнкции и т. д. Для нарушения порядка служат скобки. Рассмотрим пример. Пусть высказывания А и В имеют значения «истина», а высказывания С и Б — «ложь». Тогда формула имеет значение «ложь», т.к.:

Введя скобки, получим формулу которая уже имеет другое значение — «истина». Действительно:

Если в выражении присутствуют арифметические операции, операции сравнения и логические операции, то порядок старшинства операций следующий:

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

Например, множество точек А, заштрихованное на рис. 1.16, может быть задано следующей формулой:

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

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

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

выражает функцию от переменных А, В и С.

Такого рода функции называются булевыми, а их аргументы — булевыми переменными. Аргументы булевых функций могут представлять собой, сокращенные обозначения некоторых конкретных высказываний. Тогда функция обозначает сокращенную запись некоторого сложного высказывания. Например, делится на 3», С ? «Мурманск севернее Смоленска». В этом случае «если делится на 3 и Мурманск севернее Смоленска». Сравните с известной формулой физики где m — масса тела, а — его ускорение, а F — сила, вызвавшая это ускорение. Буквы в булевых функциях могут выступать в качестве переменных. Подставляя вместо них любые высказывания, можно по формуле вычислить соответствующее значение функции. Действительно, если в формуле «истина», Y — «ложь», Z — «истина», то — «истина». Если же Z будет иметь ложное значение, то поменяет значение на противоположное и будет «ложью».

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

Наиболее важные тождественно истинные формулы получили название Основные законы математической логики.

Основные законы математической логики

1.Коммутативность

2.Ассоциативность

3.Дистрибутивность

4.Законы де Моргана

5.Закон поглощения

6.Закон идемпотентности

8.Закон противоречия

9.Закон исключения третьего

10.Закон двойного отрицания

Пример:

Упростить выражение, используя тождественны преобразования

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

Основные методы доказательств

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

Формально каждая теорема может быть выражена в форме импликации где посылка А называется условием теоремы, а следствие В — заключением. Теорема верна, если выражающая ее импликация тождественно истинна, т. е. является тавтологией. Тавтологии рассматривают как некоторые логически истинные схемы рассуждений. В этой связи тавтологии играют роль законов, определяющих построение правильных умозаключений. Существует бесконечное множество тавтологий. Некоторые из них легли в основу методов доказательства. Основные методы доказательств.

Метод цепочек импликаций

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

В основе этого метода лежит закон цепного высказывания или закон силлогизма

Метод от противного

Метод от противного. Используя этот метод, вместо доказательства прямого следствия «из А следует В» доказывают, что из «не В» следует «не А». Этот метод основан на законе контрапозиций, имеющем следующий вид:

Метод необходимого и достаточного

Метод необходимого и достаточного. Теорема формулируется так: «Чтобы имело место А, необходимо и достаточно выполнение В». Доказательство такого вида теоремы распадается на две части:

а) доказывается, что если имеет место А, то справедливо В (В необходимо для А);

б) если имеет место В, то имеет место и А (В достаточно для А).

Доказательство таким методом базируется на законе тавтологии:

Алгебра предикатов

Предикатом заданным на множествах

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

Рассмотрим примеры, одноместный предикат на множестве комплексных чисел, при этом, например, если истинное высказывание, а

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

Всякий предикат определяет отношение R, такое, что тогда и только тогда, когда «истина». В этом случае говорят, что отношение R задается областью истинности предиката . Например, отношение «расстояние на плоскости между точками больше величины 1″ можно задать предикатом

Если в -местный предикат на место одного из термов подставить определенный элемент из соответствующего множества, то предикат станет местным. Заменив все термы на конкретные значения из предметной области предиката, получим 0 — местный предикат, т. е. высказывание. Например, «Х- брат Y» — двухместный предикат, «X — брат Маши» — одноместный предикат, «Саша — брат Маши» — высказывание.

Логические операции над предикатами

Отрицание предиката

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

Например, предикат «— четное число» есть отрицание предиката «— нечетное число» на множестве целых чисел.

Конъюнкция предикатов

Пусть на множествах заданы два — местных предиката и . Конъюнкцией этих предикатов называется предикат

который истинен для одних и тех же кортежей только тогда, когда оба предиката — и и истинны.

Например, конъюнкция предикатов где вещественные числа, определяет предикат «точки правой половины единичного круга» (см. рис. 1.17а).

Дизъюнкция предикатов

Дизъюнкция предикатов и есть новый предикат который имеет значение «ложь» для тех и только тех кортежей из для которых оба предиката — и и — имеют значение «ложь». На рис. 1.17 6 иллюстрируется дизъюнкция предиката (заштрихованная область).

Импликация предикатов

Импликация предикатов и есть новый предикат который имеет значение «ложь» для тех и только тех кортежей из для которых предикат имеет значение «истина», а предикат имеет значение «ложь».

Например, импликация « делится на 4″ —» » делится на 2″ есть предикат: «если делится на 4, то делится на 2″.

Эквивалентность предикатов

Эквивалентность предикатов и есть новый предикат который имеет значение «истина» для тех и только тех кортежей из для которых предикат и предикат имеют одинаковые значение или оба «истина» или оба «ложь». Два предиката, заданные на одних и тех же множествах, называются равносильными, если при всех наборах входящих в них предметных переменных эти предикаты принимают одинаковые значения. Равносильность называют также логической эквивалентностью. Например, эквивалентность предикатов делится на 6» и делится на 2 и делится на 3» есть предикат «если делится на 6, то делится на 2 и на 3». Предикаты логически эквивалентны.

Наряду с логическими операциями важную роль играют операции, называемые кванторами. Квантор всеобщности есть операция, которая предикат превращает в высказывание: «все обладают свойством ». Знак квантора всеобщности Он заменяет фразы: «для всех», «каждый», «любой» и т.п. Обозначение читается так: «для всех таких, что Р от ». Например, вещественное число», есть предикат « — положительное число». Тогда есть высказывание «каждое число — положительно». Это ложное высказывание. Если же — любое натуральное число то есть выражение: «каждое натуральное число — положительно» — истинное высказывание. Квантор всеобщности есть обобщение серии конъюнкций единичных высказываний. Пусть М — множество очков, которое может выпасть при бросании игральной кости, т. е. предикат: «при бросании игральной кости один раз выпадает очков», где . Применение квантора всеобщности позволяет вместо сложного высказывания записать равносильное ему компактное высказывание : «при бросании игральной кости один раз может выпасть любое из шести первых натуральных чисел».

Квантор существования

Квантор существования есть операция, которая предикат превращает в высказывание: «существует хотя бы один

из М, обладающий свойством ». Знак квантора существования Он заменяет фразы: «существует хотя бы один», «найдется», «некоторый» и т.п. Обозначение читается так: «существует хотя бы один такой, что Р от ». Например, — предикат: « — студент», где — элемент множества жителей Москвы. Тогда выражение есть высказывание «хотя бы один житель Москвы является студентом». Квантор существования есть обобщение серии дизъюнкций единичных высказываний. Если задано множество и на нем определен предикат

Кванторы обладают свойствами, являющимися аналогами законов де Моргана:

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

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

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

«каждое число делится на » — ложь;

«существует число, которое делится на » — истина;

«число делится на любое число» — ложь;

«существует число, на которое делится » — истина.

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

«каждое число делится на любое число» -ложное высказывание,

«существует число, на которое делится любое число» — истина, т.к. такое число есть 1,

«существует число, которое делится на любое число» — ложное высказывание,

«существует число, которое делится на какое-нибудь число» — истинное высказывание.

Решение заданий и задач по предметам:

• Математика
• Высшая математика
• Математический анализ
• Линейная алгебра

Дополнительные лекции по высшей математике:

1. Тождественные преобразования алгебраических выражений
2. Функции и графики
3. Преобразования графиков функций
4. Квадратная функция и её графики
5. Алгебраические неравенства
6. Неравенства
7. Неравенства с переменными
8. Прогрессии в математике
9. Арифметическая прогрессия
10. Геометрическая прогрессия
11. Показатели в математике
12. Логарифмы в математике
13. Исследование уравнений
14. Уравнения высших степеней
15. Уравнения высших степеней с одним неизвестным
16. Комплексные числа
17. Непрерывная дробь (цепная дробь)
18. Алгебраические уравнения
19. Неопределенные уравнения
20. Соединения
21. Бином Ньютона
22. Число е
23. Непрерывные дроби
24. Функция
25. Исследование функций
26. Предел
27. Интеграл
28. Двойной интеграл
29. Тройной интеграл
30. Интегрирование
31. Неопределённый интеграл
32. Определенный интеграл
33. Криволинейные интегралы
34. Поверхностные интегралы
35. Несобственные интегралы
36. Кратные интегралы
37. Интегралы, зависящие от параметра
38. Квадратный трехчлен
39. Производная
40. Применение производной к исследованию функций
41. Приложения производной
42. Дифференциал функции
43. Дифференцирование в математике
44. Формулы и правила дифференцирования
45. Дифференциальное исчисление
46. Дифференциальные уравнения
47. Дифференциальные уравнения первого порядка
48. Дифференциальные уравнения высших порядков
49. Дифференциальные уравнения в частных производных
50. Тригонометрические функции
51. Тригонометрические уравнения и неравенства
52. Показательная функция
53. Показательные уравнения
54. Обобщенная степень
55. Взаимно обратные функции
56. Логарифмическая функция
57. Уравнения и неравенства
58. Положительные и отрицательные числа
59. Алгебраические выражения
60. Иррациональные алгебраические выражения
61. Преобразование алгебраических выражений
62. Преобразование дробных алгебраических выражений
63. Разложение многочленов на множители
64. Многочлены от одного переменного
65. Алгебраические дроби
66. Пропорции
67. Уравнения
68. Системы уравнений
69. Системы уравнений высших степеней
70. Системы алгебраических уравнений
71. Системы линейных уравнений
72. Системы дифференциальных уравнений
73. Арифметический квадратный корень
74. Квадратные и кубические корни
75. Извлечение квадратного корня
76. Рациональные числа
77. Иррациональные числа
78. Арифметический корень
79. Квадратные уравнения
80. Иррациональные уравнения
81. Последовательность
82. Ряды сходящиеся и расходящиеся
83. Тригонометрические функции произвольного угла
84. Тригонометрические формулы
85. Обратные тригонометрические функции
86. Теорема Безу
87. Математическая индукция
88. Показатель степени
89. Показательные функции и логарифмы
90. Множество
91. Множество действительных чисел
92. Числовые множества
93. Преобразование рациональных выражений
94. Преобразование иррациональных выражений
95. Геометрия
96. Действительные числа
97. Степени и корни
98. Степень с рациональным показателем
99. Тригонометрические функции угла
100. Тригонометрические функции числового аргумента
101. Тригонометрические выражения и их преобразования
102. Преобразование тригонометрических выражений
103. Комбинаторика
104. Вычислительная математика
105. Прямая линия на плоскости и ее уравнения
106. Прямая и плоскость
107. Линии и уравнения
108. Прямая линия
109. Уравнения прямой и плоскости в пространстве
110. Кривые второго порядка
111. Кривые и поверхности второго порядка
112. Числовые ряды
113. Степенные ряды
114. Ряды Фурье
115. Преобразование Фурье
116. Функциональные ряды
117. Функции многих переменных
118. Метод координат
119. Гармонический анализ
120. Вещественные числа
121. Предел последовательности
122. Аналитическая геометрия
123. Аналитическая геометрия на плоскости
124. Аналитическая геометрия в пространстве
125. Функции одной переменной
126. Высшая алгебра
127. Векторная алгебра
128. Векторный анализ
129. Векторы
130. Скалярное произведение векторов
131. Векторное произведение векторов
132. Смешанное произведение векторов
133. Операции над векторами
134. Непрерывность функций
135. Предел и непрерывность функций нескольких переменных
136. Предел и непрерывность функции одной переменной
137. Производные и дифференциалы функции одной переменной
138. Частные производные и дифференцируемость функций нескольких переменных
139. Дифференциальное исчисление функции одной переменной
140. Матрицы
141. Линейные и евклидовы пространства
142. Линейные отображения
143. Дифференциальные теоремы о среднем
144. Теория устойчивости дифференциальных уравнений
145. Функции комплексного переменного
146. Преобразование Лапласа
147. Теории поля
148. Операционное исчисление
149. Системы координат
150. Рациональная функция
151. Интегральное исчисление
152. Интегральное исчисление функций одной переменной
153. Дифференциальное исчисление функций нескольких переменных
154. Отношение в математике
155. Графы в математике
156. Линейные пространства
157. Первообразная и неопределенный интеграл
158. Линейная функция
159. Выпуклые множества точек
160. Система координат