Boolean Functions and Truth-Functional Completeness

Boolean Functions and Truth-Functional Completeness

Mathematical Logic I Fall 2017

Robert Rynasiewicz

October 10, 2017

Other Connectives

So far we've seen five sentential connectives, one monadic (?) and 4 dyadic (, , and ). An n-adic connective is used to take n sentences to form a new sentence. Examples from natural language: Monadic

It is the case that . It is necessary that . It is possible that . It is obligatory that . It is permissible that God knows that . Trump believes that . Putin wants it to be the case that .

Other Natural Language Connectives (cont.)

Dyadic Neither nor . Not both and . because . That caused it to be the case that . in light of the fact that . despite the fact that . That truth-functionally entails that .

Triadic , and . , or .

An Artificial Triadic Conncetive

The majority connective: # with the recursion clause: v?(#) = M(, , ), where

M(x, y , z) =

1 if x + y + z > 1 0 otherwise

#

111 1 110 1 101 1 100 0 011 1 010 0 001 0 000 0

Truth-Functional Connectives

Def. An n-adic connective is truth-functional iff the truth value of 1 ? ? ? n is completely determined by the truth values of 1,. . . ,n.

In other words is truth-functional just in case you can write out a truth table for 1 ? ? ? n.

Which of the connectives on earlier slides are truth functional and which are not?

It is the case that . YES, v?(it is the case that ) = v?().

it is the case that

1

1

0

0

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download