**Home** / **logic proof calculator with steps** / Logic, Proofs - Northwestern University

CHAPTER 1

Logic, Proofs

1.1. Propositions

A proposition is a declarative sentence that is either true or false

(but not both). For instance, the following are propositions: "Paris

is in France" (true), "London is in Denmark" (false), "2 < 4" (true),

"4 = 7 (false)". However the following are not propositions: "what

is your name?" (this is a question), "do your homework" (this is a

command), "this sentence is false" (neither true nor false), "x is an

even number" (it depends on what x represents), "Socrates" (it is not

even a sentence). The truth or falsehood of a proposition is called its

truth value.

1.1.1. Connectives, Truth Tables. Connectives are used for

making compound propositions. The main ones are the following (p

and q represent given propositions):

Name Represented Meaning

Negation ?p "not p"

Conjunction p q "p and q"

Disjunction p q "p or q (or both)"

Exclusive Or p q "either p or q, but not both"

Implication p q "if p then q"

Biconditional p q "p if and only if q"

The truth value of a compound proposition depends only on the

value of its components. Writing F for "false" and T for "true", we

can summarize the meaning of the connectives in the following way:

6

1.1. PROPOSITIONS 7

p q ?p p q p q p q p q p q

TT F T T F T T

TF F F T T F F

FT T F T T T F

FF T F F F T T

Note that represents a non-exclusive or, i.e., p q is true when

any of p, q is true and also when both are true. On the other hand

represents an exclusive or, i.e., p q is true only when exactly one of

p and q is true.

1.1.2. Tautology, Contradiction, Contingency.

1. A proposition is said to be a tautology if its truth value is T

for any assignment of truth values to its components. Example:

The proposition p ?p is a tautology.

2. A proposition is said to be a contradiction if its truth value is F

for any assignment of truth values to its components. Example:

The proposition p ?p is a contradiction.

3. A proposition that is neither a tautology nor a contradiction is

called a contingency.

p ?p p ?p p ?p

TF T F

TF T F

FT T F

FT T F

TT

tautology contradiction

1.1.3. Conditional Propositions. A proposition of the form "if

p then q" or "p implies q", represented "p q" is called a conditional

proposition. For instance: "if John is from Chicago then John is from

Illinois". The proposition p is called hypothesis or antecedent, and the

proposition q is the conclusion or consequent.

Note that p q is true always except when p is true and q is false.

So, the following sentences are true: "if 2 < 4 then Paris is in France"

(true true), "if London is in Denmark then 2 < 4" (false true),

1.1. PROPOSITIONS 8

"if 4 = 7 then London is in Denmark" (false false). However the

following one is false: "if 2 < 4 then London is in Denmark" (true

false).

In might seem strange that "p q" is considered true when p is

false, regardless of the truth value of q. This will become clearer when

we study predicates such as "if x is a multiple of 4 then x is a multiple

of 2". That implication is obviously true, although for the particular

case x = 3 it becomes "if 3 is a multiple of 4 then 3 is a multiple of 2".

The proposition p q, read "p if and only if q", is called bicon-

ditional. It is true precisely when p and q have the same truth value,

i.e., they are both true or both false.

1.1.4. Logical Equivalence. Note that the compound proposi-

tions p q and ?p q have the same truth values:

p q ?p ?p q p q

TT F T T

TF F F F

FT T T T

FF T T T

When two compound propositions have the same truth values no

matter what truth value their constituent propositions have, they are

called logically equivalent. For instance p q and ?p q are logically

equivalent, and we write it:

p q ?p q

Note that that two propositions A and B are logically equivalent

precisely when A B is a tautology.

Example: De Morgan's Laws for Logic. The following propositions

are logically equivalent:

?(p q) ?p ?q

?(p q) ?p ?q

We can check it by examining their truth tables:

What are the components of proof calculus?Classical propositional logic Hilbert-style proof calculus consists of: A collection ofaxiom schemes. An axiom scheme is a logical scheme all whose instancesare axioms. A collection ofinference rules. An inference rule is a schema that tells one how onecan derive new formulas from formulas that have already been derived.

Title: discmath_dvi

Producer: PStill 1.55.9 - private/edu use only

CreationDate: Tue May 24 15:24:51 2005

Tagged: no

Form: none

Pages: 5

Encrypted: no

Page size: 612 x 792 pts (letter) (rotated 0 degrees)

File size: 229552 bytes

Optimized: no

PDF version: 1.1