ОСНОВЫ ЛОГИКИ

Построение Клики.

Клика

Клика- максимально большой полный подграф данного графа.

a

f b

e c

d

	a	b	c	d	e	f
a
b
c
d
e
f

1. Строим дополнительный граф исходного графа.

G a

f b

e c

d

2. Найдем множество внутренней устойчивости для графа G.

(a Ú d)(a Ú e)(a Ú f)(b Ú c)(c Ú d)

(a Ú de)(a Ú f)(c Ú bd)

(a Ú def)(cÚ bd)

ac Ú cdef Ú bdef Ú abd

{b, d, e, f}, {c, e, f}, {a, b}, {a, c}

3. Множества полученных вершин дают всевозможные полные подграфы исходного графа G. Причем, максимальный из подграфов дает клику.

Логика – наука о законах и формах мышления

Высказывание (суждение) – некоторое предложение, которое может быть истинно (верно) или ложно

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

Рассуждение – цепочка высказываний или утверждений, определенным образом связанных друг с другом

Умозаключение– логическая операция, в результате которой из одного или нескольких данных суждений получается (выводится) новое суждение

Логическое выражение – запись или устное утверждение, в которое, наряду с постоянными, обязательно входят переменные величины (объекты). В зависимости от значений этих переменных логическое выражение может принимать одно из двух возможных значений: ИСТИНА (логическая 1) или ЛОЖЬ (логический 0)

Сложное логическое выражение – логическое выражение, составленное из одного или нескольких простых (или сложных) логических выражений, связанных с помощью логических операций.

Дадим определения операциям логики высказываний и постоим для них таблицы истинности.

Опр. Отрицанием функции f (инерцией) назовем новую функцию , которая принимает значение 1, если f равна 0, и значение 0, если f равна 1.

Опр. Конъюнкцией 2-х переменных называется функция f(x₁,x₂)= x₁x₂, которая принимает значение 1, если и только если обе переменные равны 1 (и, значит, равна 0, если хотя бы одна из этих переменных равна 0).

Опр. Дизъюнкцией 2-х переменных называется такая функция f(x₁,x₂)= x₁x₂ , которая принимает значение 0, если и только если обе переменные равны 0 (и, значит, равна 1, если хотя бы одна из этих переменных равна 1).