Связь теории высказываний и теории множеств

Теорема. Пусть одна некоторая формула логики высказываний, которая не содержит импликацию и эквивалентность. Каждой из переменных поставим в соответствие какое-либо множество.

Заменим Ai на Bi; ∨ на⋃; ∧ на ⋂

Получим Т(В1,…,Вn)

Пусть Ai: х⊂Bi, тогда F-истинно⟷x⊂T

Пример

F=A1∨A2

T=B1⋃B2

Доказательство от противного

Пусть не так. Пусть F-формула,для которой заключение не выполняется и которая содержит наименьшее число операций, заметим, что F-неэлементарная формула (если F=Ai, то T=Bi и F удовлетворяет условию теоремы).

Тогда или F=G или F=G1∨G2 или F= G1∧G2

И при том в G операций меньше, чем в F=> для Gi выполнено условие теоремы:

Пусть F=G1→F=И⟷G1=Л⟷x T(G)

T(F)=T(G)⟷x T(F)

Пусть F=G1∨G2, T(F)=T(G1) ⋃T(G2)