**Home** / **logic proof calculator with steps** / Logic, Sets, and Proofs - Amherst College

Logic, Sets, and Proofs

David A. Cox and Catherine C. McGeoch

Amherst College

1 Logic

Logical Operators. A logical statement is a mathematical statement that can be

assigned a value either true or false. Here we denote logical statements with capital

letters A, B. Logical statements be combined with the following operators to form

new logical statements.

Operation name Notation I Notation II Java

AND (Conjunction) A B A ? B A && B

OR (Disjunction) A B A + B A || B

NOT (Negation) ?A A? !A

IMPLIES (Implication) A B if A then B

IF AND ONLY IF (Equivalence) A B A iff B ==

Tautologies. Here is a list of tautologies. In any proof, you can replace a statement

in the first column with the corresponding statement in the second column, and vice

versa. All of these can be proved by truth tables.

Statement Equivalent statement Description

A B B A is commutative

A B B A is commutative

(A B) C A (B C) is associative

(A B) C A (B C) is associative

A (B C) (A B) (A C) distributes over

A (B C) (A B) (A C) distributes over

A false A false is identity for

A true A true is identity for

A ?A true law of excluded middle

A ?A false contradiction

A A A is idempotent

A A A is idempotent

??A A double negative

?(A B) ?A ?B De Morgan's law for

?(A B) ?A ?B De Morgan's law for

A B ?A B rewriting implication

A B ?B ?A contrapositive

A (B C) (A B) C conditional proof

A B (A B) (B A) definition of

1

2 Sets

A set is a collection of objects, which are called elements or members of the set. Two

sets are equal when they have the same elements.

Common Sets. Here are three important sets:

? The set of all integers is Z = {. . . , -3, -2, -1, 0, 1, 2, 3, . . .}.

? The set of all real numbers is R.

? The set with no elements is , the empty set.

Another important set is the set of natural numbers, denoted N or N . Unfortunately,

the meaning of N is not consistent. In some books,

N = {1, 2, 3, . . .},

while in other books,

N = {0, 1, 2, 3, . . .}.

Basic Definitions and Notation.

? x S: x is an element or member of S. Example: 2 Z.

1 / Z.

? x / S: x is not an element of S, i.e., ?(x S). Example: 2

? S T : Every element of S is also an element of T . We say that S is a subset

of T and that T contains or includes S. Examples: Z R and Z Z.

? S T : This means ?(S T ), i.e., some element of S is not an element of T .

Example: R Z.

? S T : This means (S T ) (S = T ). We say that S is a proper subset of T

and that T properly contains or properly includes S. Example: Z R.

Note that S = T is equivalent to (S T ) (T S).

Describing Sets. There are two basic ways to describe a set.

? Listing elements: Some sets can be described by listing their elements inside

brackets { and }. Example: The set of positive squares is {1, 4, 9, 16, . . .}. When

listing the elements of a set, order is unimportant, as are repetitions. Thus

{1, 2, 3} = {3, 2, 1} = {1, 1, 2, 3}

since all three contain the same elements, namely 1, 2 and 3.

2

? Set-builder notation: We can sometimes describe a set by the conditions its

elements satisfy. Example: The set of positive real numbers is

{x R | x > 0}.

This can also be written {x | (x R) (x > 0)}. A common alternative

notation uses the colon instead of the vertical bar, as in {x : (x R) (x > 0)}.

Operations on Sets. Let S and T be sets.

? The union S T is the set

S T = {x | (x S) (x T )}.

Thus an element lies in S T precisely when it lies in at least one of the sets.

Examples:

{1, 2, 3, 4} {3, 4, 5, 6} = {1, 2, 3, 4, 5, 6}

{n Z | n 0} {n Z | n < 0} = Z.

? The intersection S T is the set

S T = {x | (x S) (x T )}.

Thus an element lies in S T precisely when it lies in both of the sets. Examples:

{1, 2, 3, 4} {3, 4, 5, 6} = {3, 4}

{n Z | n 0} {n Z | n < 0} = .

? The set difference S - T is the set of elements that are in S but not in T .

Example:

{1, 2, 3, 4} - {3, 4, 5, 6} = {1, 2}.

A common alternative notation for S - T is S \ T .

3 Predicates and Quantifiers

A variable like x represents some unspecified element from a fixed set U called the

universe. A predicate is a logical statement containing one or more variables. Exam-

ples: "x is even" and "x > y" are predicates. The truth of the predicate depends on

which particular members of the universe are plugged in for the variables.

We combine quantifiers with predicates to form statements about members of U .

There are two basic types:

3

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.

Creator: TeX

Producer: pdfTeX-0.14h

CreationDate: Sun Jan 25 14:41:00 2009

Tagged: no

Form: none

Pages: 10

Encrypted: no

Page size: 595.276 x 841.89 pts (A4) (rotated 0 degrees)

File size: 94058 bytes

Optimized: no

PDF version: 1.3