CS计算机代考程序代写 python Java Haskell Propositional Logic – COMP1600 / COMP6260

Propositional Logic – COMP1600 / COMP6260

Propositional Logic
COMP1600 / COMP6260

Dirk Pattinson Victor Rivera
Australian National University

Semester 2, 2021

This Course

Programming. (Haskell, Java, Python, . . . )

Tell the computer how to perform a certain task

Logic. (this course)

Specify precisely what task should be performed

Computation. (this course)

the (discrete) maths of computation: what can be done in principle?

You know how to program. We will explore logic to describe programs,
and study fundamental (programming language independent) models of
what can be computed in the first place.

2 / 32

Example: Vote Counting in the ACT

/* STEP 19 */

/* We haven’t incremented count yet, so this applies to NEXT count */

mark_elected(cand, (void *)(count+1));

/* STEP 20 */

vote_value_of_surplus = cand->c[count].total – quota;

/* STEP 21 */

increment_count();

/* STEP 22 */

pile = cand->c[cand->count_when_quota_reached].pile;

non_exhausted_ballots

= (number_of_ballots(pile)

– for_each_ballot(pile, &is_exhausted, candidates));

/* STEP 23 */

if (non_exhausted_ballots == 0)

new_vote_value = fraction_one;

else

new_vote_value = ((struct fraction) { vote_value_of_surplus,

non_exhausted_ballots });

/* STEP 24 */

update_vote_values(pile, new_vote_value);

/* STEP 24b */

/* Report actual value (may be capped) */

report_transfer(count,

pile->ballot->vote_value,

vote_value_of_surplus);

distribute_ballots(pile, candidates,vacating);

(Part of the EVACS code used for vote counting in the ACT in 2012)

Do you trust this? What does it do? Does it really implement the law?

3 / 32

The two faces of Boolean logic: Circuits

“Computation with boolean / binary values: 0 and 1”

4 / 32

The two faces of Boolean logic: Formulae

George Boole (1815 – 1864)

“Logic” as a way of reasoning
about true statements

at the time: mathematical
statements

here: statements about
computer programs

“All statements are either true
or false: T / F ”

5 / 32

Truth Values

Consider binary, or boolean values

0, or false (written F )

1, or true (written T )

Boolean Functions are functions that

take boolean values as inputs (zero, or more)

produce boolean values as outputs (generally, one or more)

Example.

x y f (x , y)

0 0 0
0 1 1
1 0 1
1 1 0

x y f (x , y)

F F F
F T T
T F T
T T F

6 / 32

Two Interpretations

Example. x y f (x , y)
0 0 0
0 1 1
1 0 1
1 1 0

x y f (x , y)

F F F
F T T
T F T
T T F

Computation with Binary Values

the output is 1 if precisely one of the inputs (but not both) is 1

or: considering x and y as one-bit numbers, the output is the sum
x + y taken modulo two.

Truth of Statements
Here, x and y represent whether certain statements are true or false, e.g.:

x could stand for “Joe was born in Melbourne”

y could stand for “Joe was born in Sydney”

Then f (x , y) is the truth value of the statement “Joe was born either in
Sydney or in Melbourne”

7 / 32

More on the Two Interpretations

Computing with Binary Values.

inputs are either 0 or 1

one output is prescribed for each combination

used to describe computation

Truth of Statements

inputs describe whether certain statements are true or false

output describes the truth value of a compound statement

used to describe truth

8 / 32

Building Boolean Functions

As with writing programs, boolean functions are constructed from basic
building blocks

x AND y

x y x ∧ y
0 0 0
0 1 0
1 0 0
1 1 1

x OR y

x y x ∨ y
0 0 0
0 1 1
1 0 1
1 1 1

NOT x

x ¬x
0 1
1 0

AND, OR and NOT are written as ∧, ∨ and ¬, respectively and
called conjunction, disjunction and negation.

the symbols in the last row are circuit representations

9 / 32

Example revisited

x y f (x , y)

0 0 0
0 1 1
1 0 1
1 1 0

x y f (x , y)

F F F
F T T
T F T
T T F

Written as Logical Formulae

(x ∧ ¬y) ∨ (¬x ∧ y)

Reading of the Formula. This formula is true in a situation

where either the LHS (i.e. x ∧¬y) is true, or the RHS (i.e. ¬x ∧ y) is
true, or both (!)

the LHS is true if x is true and ¬y is true (so y is false)
the RHS is true if ¬x is true (so x is false) and y is true
so that the formula is true in a situation where precisely one of x and
y are true (but not both)

10 / 32

About Situations

Recall. Truth of the formula (x ∧ ¬y) ∨ (¬x ∧ y) depends on a situation
that tells us which variables are true and false

can evaluate a formula to either true or false in any situation

Definition. If V is a set of variables (e.g. V = {x , y} for the formula
above), then a situation for V is a mapping s : V → {T,F}

11 / 32

Formula View

Q. How do we align the formula and the boolean function?
A. Construct the value of the boolean function step by step

x y ¬x ¬y x ∧ ¬y ¬x ∧ y (x ∧ ¬y) ∨ (¬x ∧ y)
F F T T F F F

F T T F F T T

T F F T T F T

T T F F F F F

Left two columns: all possible truth values for x and y

given y , we know ¬y (4th column)
given x and ¬y , we know x ∧ ¬y (penultimate column)
given x , we know ¬x (3rd column)
given ¬x and y , we know ¬x ∧ y (6th column)
given x ∧¬y , and ¬x ∧ y , we know (x ∧¬y)∨ (¬x ∧ y) (last column)

Indeed, (x ∧ ¬y) ∨ (¬x ∧ y) is exclusive-or!
12 / 32

Formula View, Continued

(x ∧ ¬y) ∨ (¬x ∧ y)

Q. What columns do I need?

A. Look at the target formula . . .

to evaluate (x ∧ ¬y) ∨ (¬x ∧ y), we need both x ∧ ¬yand ¬x ∧ y
to evaluate x ∧ ¬y , we need x (given) and ¬y
to evaluate ¬x ∧ y , we need ¬x and y (given)

Coloured formulae indicate columns in the table.

More systematically

1 start with the target formula, and create entries for immediate
subformulae

2 repeat step 1 for all subformulae until inputs are reached.

13 / 32

Truth Tables

Formulae. Are constructed from T (true), F (false) and variables
(x , y , . . . ) using ∧,∨,¬ (more connectives later).

Truth Tables for a formula

list all T/F combinations of the variables (all situations)

list the truth value of the formula, given variable values

possibly list truth values of subformulae, too

Example. (same as before)

x y ¬x ¬y x ∧ ¬y ¬x ∧ y (x ∧ ¬y) ∨ (¬x ∧ y)
F F T T F F F

F T T F F T T

T F F T T F T

T T F F F F F

14 / 32

On Representation

Boolean Functions with n inputs are simply functions:

f : {0, 1} × · · · × {0, 1}︸ ︷︷ ︸
n times

→ {0, 1}.

Logical Formula with n variables represent boolean functions

the truth table of the formula defines a boolean function

many representations of the same boolean function!

Circuits with n inputs also represent boolean functions

one boolean output is determined for each combination of inputs

again, can have many circuits representing the same function

Summary. Boolean functions can be represented by truth tables
(uniquely), formulae and circuits.

15 / 32

More Circuit Primitives

x XOR y

x y xor(x , y)

0 0 0
0 1 1
1 0 1
1 1 0

x NAND y

x y nand(x , y)

0 0 1
0 1 1
1 0 1
1 1 0

(x∧¬y)∨(¬x∧y) ¬(x ∧ y)
we don’t introduce formula type connectives for NAND and XOR as
they are not commonly used (and we will not use them in what
follows), but they can be encoded

the symbols in the middle row are the circuit representations

16 / 32

Can We Express All Boolean Functions?

Q. Given a boolean function f (x1, . . . , xn), can we construct a formula
that represents f ?

A. Yes, this is a theorem and here is the proof. Recall that a formula
represents a function if the truth table of the formula gives precisely the
function table.

Proof (Sketch).
For boolean values i1, . . . , in ∈ {T ,F} we have a formula φi1…in such that

φi1…in(x1, . . . , xn) = T ⇐⇒ x1 = i1 and . . . and xn = in.

(This formula is a large ∧ with elements x` if i` = T and ¬x` if i` = F .)

Then take φf = φr1 ∨ · · · ∨ φrk where r1, . . . , rk are precisely the vectors
(i1, . . . , in) for which f (i1, . . . , in) = T .

17 / 32

Proof Detail

Suppose we have a line of the truth table

x y z f (x , y , z)

T T F T

Consider the formula
φTTF ≡ x ∧ y ∧ (¬z)

then we have

φTTF = T if and only if x = T , y = T , z = F

18 / 32

Proof Detail

Now consider all lines of the truth table

x y z f (x , y , z)

. . .

T T F T

. . .

T F F T

. . .

F F F T

. . .

that have a T in the right hand column, where lines that are not shown
have a F in the right column. The formula

φTTF ∨ φTFF ∨ φFFF
has precisely the truth table above.

19 / 32

Expressively Complete Sets

Definition. A set of logical connectives is expressively complete if it allows
us to build all boolean functions.

Example. The set consisting of ∧, ∨ and ¬ expressively complete.

Non-example. The sets consisting just of ¬, and just of ∨, are not
expressively complete.

Theorem. The set consisting of just nand is expressively complete.

Proof (Sketch). Using formula notation, we can use nand to

express negation: ¬x = nand(x , x)
express conjunction: x ∧ y = ¬nand(x , y)
express disjunction: x ∨ y = ¬(¬x ∧ ¬y)

20 / 32

Elements of Counting

Q1. How many boolean functions with n inputs (and one output) can we
create using AND, OR and NOT circuits / using the logical connectives ∧,
∨, and ¬?

Q2. How many boolean functions with n inputs (and one output) can we
create just with OR-gates and a constant wire with value 0 / the logical
connectives ∨ and F?

Q3. How many gates do we need in the worst case to construct a boolean
function?

21 / 32

A Formula-Size Theorem

Theorem. Every boolean function with n input bits (and one output) can
be represented using at most 10 · 2n − 10 logical connectives from the set
{¬,∧,∨}.

Proof (Sketch). We use a technique called induction that we will analyse
more closely later in the course.
Base case: n = 1. We can build every one-bit function using at most
10 · 21 − 10 = 10 connectives.
Inductive Step: n > 1. By fixing the first bit of f to be 0 and 1, we have
two n − 1-bit functions f0 and f1:

f0(x2, . . . , xn) = f (0, x2, . . . , xn) f1(x2, . . . , xn) = f (1, x2, . . . , xn)

Both can be represented using at most 10 · 2n−1 − 10 connectives.
We can write f = (¬x1 ∧ f0)∨ (x1 ∧ f1). Using f0 and f1, we therefore need
to add 4 more connectives to get a formula for f , and we have used

2 · (10 · 2n−1 − 10) + 4 = 10 · 2n − 20 + 4 ≤ 10 · 2n − 10
connectives.

22 / 32

Visualisation: Venn Diagrams

x y

x ∧ y
x y

x ∨ y
x

¬x
the boxes are the space of all situations where x and y are true or false

labelled circles describe those situations where x and y are true

red area describes those situations where the formula is true.

(Every point in a Venn diagram describes a situation).

23 / 32

Memories from High School . . .

Analogy: Algebraic Terms. Given a set V of variables, algebraic terms
are constructed as follows:

0, 1, . . . and all variables x ∈ V are algebraic terms
if s and t are algebraic terms, then so is s + t and s · t.

Example.

5 + (3 · x) x (x · (3 · (7 + 5))) + z

Usual precedence. · binds more strongly than +:

x · 3 + y reads as (x · 3) + y

Crucial Aspect.

Terms can be evaluated given values for all variables.

24 / 32

Back to Boolean Functions

Definition. Given a set V of variables, boolean formulae are constructed
as follows:

T (true) and F (false) and all variables x ∈ V are boolean formulae
if φ and ψ are boolean formulae, then so are φ ∧ ψ and φ ∨ ψ.
if φ is a boolean formula, then so is ¬φ.

Examples.

T ∨ ¬(x ∨ (¬y)) x x ∧ ¬(T ∨ (F ∨ x))

Precedence. ¬ binds more strongly than ∧ binds more strongly than ∨:

¬x ∧ y ∨ z reads as ((¬x) ∧ y) ∨ z

Crucial Aspect.

Boolean formulae can be evaluated given (boolean) values for all
variables.

25 / 32

Equations

Examples from Algebra.

x · (3 + y) = x · 3 + x · y
25 + (18 · y) = 18 · y + 25

Boolean Equations. have boolean formulae on the left and right:

x ∧ (y ∨ x) = x
T ∧ (y ∨ x) = x ∨ y

Valid Equations.

For all values of variables, LHS and RHS evaluate to same number.

Applies to both algebraic terms and boolean formulae!

26 / 32

Valid Boolean Equations.

Associativity

a ∨ (b ∨ c) = (a ∨ b) ∨ c a ∧ (b ∧ c) = (a ∧ b) ∧ c

Commutativity

a ∨ b = b ∨ a a ∧ b = b ∧ a

Absorption.

a ∨ (a ∧ b) = a a ∧ (a ∨ b) = a

Identity.

a ∨ F = a a ∧ T = a

Distributivity.

a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c) a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c)

Complements.

a ∨ ¬a = T a ∧ ¬a = F
27 / 32

Equational Reasoning in Ordinary Algebra

(x + 12) · 3(x + 17)
= (x + 12) · (3 · x + 3 · 17) (distributivity)
= (x + 12) · (3 · x + 51)
= x · (3 · x + 51) + 12 · (3 · x + 51) (distributivity)
= x · 3 · x + x · 51 + 12 · 3 · x + 12 · 51 (distributivity)
= 3 · x2 + 51 · x + 36 · x + 612 (commutativity)
= 3 · x2 + (51 + 36) · x + 612 (distributivity)
= 3 · x2 + 87 · x + 612

each step (other than addition / multiplication of numbers) justified
by a “law of arithmetic”

“pattern matching” against algebraic laws

28 / 32

Proving Boolean Equations

Example. We prove the law of idempotence:

x ∨ x = (x ∨ x) ∧ T (identity)
= (x ∨ x) ∧ (x ∨ ¬x) (complements)
= x ∨ (x ∧ ¬x) (distributivity)
= x ∨ F (complements)
x (identity)

Rules of Reasoning.

All boolean equations may be assumed (with variables substituted by
formulae)

may replace formulae with formulae that are proven equal

equality is transitive!

29 / 32

Two faces of boolean Equations

Truth of boolean equations:
A boolean equation φ = ψ (where φ, ψ are boolean formulae) is true if φ
and ψ evaluate to the same truth values in all situations (i.e. for all
possible truth values of the variables that occur in φ and ψ).

Equational Provability of boolean equations:
A boolean equation is provable if it can be derived from associativity,
commutativity, absorption, identity, distributivity and complements using
the laws of equational reasoning.

Q. How do these two notions hang together?

30 / 32

Soundness and Completeness

Slightly Philosophical.

Truth of an equation relates to the meaning (think: truth tables) of
the connectives ∧,∨ and ¬.
Equational provability relates to a method that allows us to establish
truth of an equation.

They are orthogonal and independent ways to think about equations.

Soundness. If a boolean equation φ = ψ is provable using equations, then
it is true.

all basic equations (associativity, distributivity, . . . ) are true

the rules of equational reasoning preserve truth.

Completeness. If a boolean equation is true, then it is provable using
equations.

more complex proof (not given here), using the so-called Lindenbaum
Construction.

31 / 32

Challenge Problem: The De Morgan Laws

De Morgan’s Laws

¬(x ∨ y) = ¬x ∧ ¬y ¬(x ∧ y) = ¬x ∨ ¬y

In English

if it is false that either x or y is true, they must both be false

if it is false that both x and y are true, then one of them must be
false.

Truth of De Morgan’s Laws: Easy to establish via truth tables.

Provability of De Morgan’s Laws

if the completeness theorem (that we didn’t prove!) is true, then an
equational proof must exist

however, it is quite difficult to actually find it!

32 / 32