Краткая методичка по логике - (шпаргалка)
p>uv обозначает результат написания выражения v после выражения u.Термами называются знакосочетания с такими порождающими правилами: D х
D c
D u1, …, un, f (u1, … , un). f n-местный, n№0.
Обозначения для термов: a, b, a0, b0, a1, b1, …
Пример индуктивной последовательности термов:
f
c1
f (c1, f)
f (c1, c1, f(c1, f))
c2
f(c1, f, f(c1, f), c2)
f(c2)
f(f(c2))
Высказываниями, соотношениями, формулами называются знакосочетания с такими правилами порождения:
D g здесь g нульместный
D g(а1, …, аn) здесь g n-местный, n№0
D u, "x(u)
D u, $x(u)
D u, Ш(u)
D u, v, (u)Щ(v)
D u, v, (u)Ъ(v)
D u, v, (u)Ю(v)
D u, v, (u)Ы(v)
Примериндуктивной последовательности формул (на основе термов из предыдущего примера)
g(f, c1)
g
"c5(g)
$c1(g(f, c1))
Ш("c5(g))
g
(g)Ъ("c5(g))
g(f(c1, f), c2, c2)
Обозначениями для высказываний: p, q, r, s, t, p0, q0, r0, s0, t0, … С целью удобства обозрения формул некоторые скобочные диады можно опускать, принимая соглашение о правосторонней группировке скобок для нескольких одинаковых логических знаков и соглашение об убывании силы связи в алфавитном порядке логических знаков. Пример: pЮqЮr означает (p)Ю((q)Ю(r)), а запись Ш$xpЪqЩr понимается как (Ш($x(p)))Ъ((q)Щ(r)). Следует помнить, что любое высказывание с пропущенными парами скобок не является высказыванием формального языка, оно является лишь обозначением соответствующего высказывания.
Нульместные функциональные знаки называются константами. Знакосочетание "x называется квантором всеобщности по х, а $х - квантором существования по х. Начинающееся с предикатного знака высказывание называется предикатом. Высказывание называется элементарным, если оно начинается с квантора или предикатного знака. Высказывание q называется подвысказыванием или компонентой высказывания р, если q есть часть р. Элементарная компонента q высказывания р называется его пропозициональной компонентой, если q имеет хотя бы одно такое вхождение в р, которое не является вхождением в какую-нибудь другую элементарную компоненту высказывания р. Например, высказывание$c5(gЩg)Юg имеет пять компонент: $c5(gЩg), g, g, gЩg, $c5(gЩg)Юg, из которых только первые три являются элементарными, первые две пропозициональными, только g и g - предикатными.
Интерпретацияформального языка. Переменная выражает, нотирует, обозначает произвольный объект из некоторого не пустого множества, которое называется денотарием или универсумом данной интерпретации и элементы которого тем самым являются денотатами или значениями переменной. n-местный функциональный знак обозначает n-местную операцию на универсуме. n-местный предикатный знак обозначает изначальную взаимосвязь между любыми n объектами универсума. Термы обозначают объекты универсума, а высказывания обозначают истину или ложь, т. е. денотатами термов являются объекты универсума, а денотатами высказываний являются истина и ложь. Задать интерпретацию формального языка значит задать ее универсум и связанные с ним значения всех нужных нам функциональных и предикатных знаков; тогда значения всех нужных термов и формул при любых значениях фигурирующих в них переменных определяются индукцией по их построению с учетом такой интерпретации логических знаков:
"xp - обобщение высказывания р по х является истинным тттк р является истинным для всех значений переменной х; синонимы: р для каждого х, р для любого х, р для всех x, р для произвольного х.
$xp - подтверждение высказывания р по х является истинным тттк р является истинным хотя бы для одного значения переменной х; синонимы: существует х т. ч. р, р для некоторого х.
Шp - отрицание высказывания р является истинным тттк р является ложным; синонимы: не р, неверно что р.
pЩq - конъюнкция высказываний р, q является истинной тттк оба ее конъюнкта р, q являются истинными; синонимы: р и q, и р и q.
pЪq - дизъюнкция высказываний p, q является ложной тттк оба ее дизъюнкта р, q являются ложными; синонимы: р или q, или р или q.
pЮq - импликация высказываний p, q является ложной тттк посылка р является истинной, а заключение q является ложным; синонимы: р только если q, если р то q, q если р, р тогда q, q когда р, для того чтобы р необходимо чтобы q, для того чтобы q достаточно чтобы р, р следовательно q, из того что р следует что q.
pЫq - эквиваленция высказываний р, q является истинной тттк ее части р, q обе являются истинными или обе являются ложными; синонимы: р если и только если q, р тогда и только тогда когда q, для того чтобы р необходимо и достаточно чтобы q, р эквивалентно q.
Замечание. Иногда высказывания записывают на смеси формального, обычного и математического языка. Все такие записи будем рассматривать как обозначения соответствующих высказываний формального языка.
Замечание. Введение обозначений для высказываний порождает двусмысленность в использовании знака равенства, поскольку сами высказывания являются некоторыми обозначениями, а именно обозначениями истины или лжи. При наличии иерархии обозначений такую двусмысленность обычно снимают соглашением о том, что равенство понимается как равенство между исходными объектами. Т. о. равенство p=q означает, что р и q имеют одинаковые истинностные значения т. е. являются равносильными. Пример. Каждый кулик свое болото хвалит.
Универсум - множество куликов и болот
g(x) - х есть кулик
g(x) - х есть болото
g(x, у) - х хвалит у
g(x, у) - у свое для х
"c1((((g(c1))Щ(g(c2)))Щ(g(c1, c2)))Ю(g(c1, c2)))
Пример. Сумма квадратов двух положительных чисел меньше квадрата их суммы. Универсум - множество положительных чисел.
f(x) - квадрат числа x
f(x, y) - сумма чисел x, y
g(x, y) – x меньше y
g(f(f(c1), f(c2)), f(f(c1, c2)))
Можно записать по-другому:
универсум - множество действительных чисел
f - число 0
((g(f, c1))Щ(g(f, c2)))Ю(g(f(f(c1), f(c2)), f(f(c1, c2)))
Пример. Только я один знаю об этом.
Универсум – множество людей
f - я
g(x) - x знает об этом
g(x, y) - x идентичен y
(g(f))Щ("c1((Ш(g(c1, f)))Ю(Ш(g(c1))))
Никто не знает об этом: "c1(Ш(g(c1)))
Все знают об этом: "c1(g(c1))
Кто-нибудь знает об этом: $c1(g(c1))
Пример. Здесь холодно, но не сыро: (g)Щ(Ш(g))
Пример. Ни p ни q: Шp и Шq
Пример. Если p то q иначе r: (pЮq)Щ(ШpЮr)
Пример. p либо q: pЩШqЪШpЩq
Пример. p поэтому q: pЩ(pЮq)
Пример. Чай без сахара не сладкий и не вкусный.
g - чай содержит сахар
g - чай сладкий
g - чай вкусный
(Ш(g))Ю((Ш( g))Щ(Ш( g)))
Возможен другой перевод:
((Ш(g))Ю(Ш( g)))Щ((Ш( g))Ю((Ш( g)))
Пример. Его отец слесарь, а все братья токари.
Универсум – множество мужчин
f - он
f(x) - отец для x
g(x) - x есть слесарь
g(x) - x есть токарь
g(x, y) - x идентичен y
(g(f(f)))Щ("c1(((Ш(g(c1, f)))Щ(g(f(c1), ( f(f))))Ю(g(c1))))
Тема 3. Пропозициональная логика
или логика элементарных высказываний изучает свойства логических операций Ш, Щ, Ъ, Ю, Ы, которые по смыслу их введения являются операциями над истинностными значениями:
p
q
Шp
pЩq
pЪq
pЮq
pЫq
Л
Л
И
Л
Л
И
И
Л
И
И
Л
И
И
Л
И
Л
Л
Л
И
Л
Л
И
И
Л
И
И
И
И
Если высказывания р, q различны и элементарны, то эта таблица называется истинностной таблицей высказываний (p, q, )Шp, pЩq, pЪq, pЮq, pЫq. В общем случае при составлении истинностной таблицы какого-либо перечня высказываний надо поместить на ее вход все различные пропозициональные компоненты этих высказываний, сделать полный перебор истинностных значений во входных столбцах и записать соответствующие истинностные значения в результирующих столбцах.
Пример. В комнате без окон темно и неуютно.
Универсум - множество комнат
g(c1) - c1 имеет окно p - комната имеет окно
g(c1) - в c1 темно q - в комнате темно
g(c1) – в c1 уютно r - в комнате уютно
(Ш(g(c1)))Ю((g(c1))Щ(Ш(g(c1)))) ШpЮqЩШr
p q r
p
q
r
Шp
Шr
qЩШr
ШpЮqЩШr
Л
Л
Л
И
И
Л
Л
Л
Л
И
И
Л
Л
Л
Л
И
Л
И
И
И
И
Л
И
И
И
Л
Л
Л
И
Л
Л
Л
И
Л
И
И
Л
И
Л
Л
Л
И
И
И
Л
Л
И
И
И
И
И
И
Л
Л
Л
И
