Порядок выполнения операций

Если в сложном выражении скобок нет, то операции надо выполнять в следующем порядке: конъюнкция, дизъюнкция, импликация, эквивалентность, отрицание.

Соглашения относительно расстановки скобок.

1. Внешние скобки не пишутся.

Пример. Вместо пишут

2. На множестве вводятся транзитивное отношение < «быть более сильным» и отношение эквивалентности ~ «быть равносильным» по правилам показанным на рис.

~ ~

~

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

Конечность области определения функции имеет важное преимущество – такие функции можно задавать перечислением значений при различных значениях аргументов. Для того, чтобы задать значение функции от n переменных, надо определить значения для каждого из 2 ⁿ наборов. Эти значения записывают в таблицу в порядке соответствующих двоичных чисел. В результате получается таблица следующего вида:

Булева функция f(x₁, x₂, …,x_n) полностью определяется своей таблицей истинности

x1	x2	x3	…	xn-1	xn	f(x1, x2, …,xn)
			…			f(0, 0, … 0, 0)
			…			f(0, 0, … 0, 1)
. . .	. . .	. . .	… … …	. . .	. . .	. . .
			…			f(1, 1, … 1, 0)
			…			f(1, 1, … 1, 1)

В каждой строке таблицы истинности задается набор значений переменных (δ₁,δ₂, …,δ_n), а затем - значение функции на этом наборе.

Если булева функция f и формула φ имеют одну и ту же таблицу истинности, то формула φ представляет функцию f.