Логіка і множини

реферат

6. Логіка квантифікаторів

Повернемось до прикладу "x є парне число". Обмежимо x множиною цілих чисел Z . Tоді вислів "x є парне число" істинний лише для деяких x в Z. Звідси слідує, що вислів "деякі x ЎК Z парні" істинний, якщо вислів "всі x ЎК Z непарні" хибний.

В загальному випадку розглянемо функцію вислів p(x) в якій змінна x належить певній множині. Введемо наступні позначення для висловів

?x, p(x) (для всіх x, p(x) істинний);

і

?x, p(x) (для деяких x, p(x) істинний).

Символ ? (для всіх) і ? (для деяких) називаються відповідно універсальним квантифікатором і квантифікатором існування. Зауважимо, що змінна x не є суттєва, вона може бути замінена будь якою іншою, так що ?x, p(x) і ?y, p(y) означають одне й те ж саме.

(Теорема Лагранжа) Кожне натуральне число є сума квадратів чотирьох цілих чисел. Це можна записати як

?n ЎК N, ?a, b, c, d ЎК Z, n = a2 + b2 + c2 + d2.

(Гіпотеза Гольдбаха) Кожне парне число більше 2 є сума двох простих чисел. Це можна записати як

?n ЎК N {1}, ?p, q прості, 2n = p + q.

Ще невідомо, чи це дійсно так. Це одна з найцікавіших з ще не розвязаних проблем математики.

Заперечення

Розглянемо заперечення висловів з квантифікаторами. Давайте скажемо, що всі люди дурні. Дехто з вас з цим не погодиться. Можна здогадатися, що запереченням вислову ?x, p(x) буде вислів ?x, p(x). Тепер будемо не так категоричними і скажемо, що дехто з вас дурень. Якщо і цього разу заперечите, то запереченням вислову ?x, p(x) буде ?x, p(x). Отже, маємо формули аналогічні законам де Моргана для квантіфікаторів

?x, p(x) ?x, p(x)

?x, p(x) ?x, p(x).

Підсумовуючи сказане, заперечуючи вислів з кавантифікатрором ми змінюємо квантифікатор і заперечуємо функцію висловів. Застосовуючи це правило послідовно декілька раз одержимо заперечення більш складного вислову

спочатку як

Потім

Потім

і, нарешті,

Запереченням гіпотези Гольдбаха в термінах квантифікаторів буде

?n ЎК N {1}, ?p, q прості числа, 2n p + q.

Іншими словами, існує парне число більше 2, яке не є сумою двох простих чисел. Отже, щоб відкинути гіпотезу Гольдбаха досить знайти таке число. Це називається "привести контр приклад".

Делись добром ;)