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

---

• (1) Logic proof generator solver
• (2) Formal proof calculator
• (3) Logic direct proof calculator
• (4) Proof solver for formal logic

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.

• Logic, Proofs, and Sets - Department of Mathematics
• Logic, Sets, and Proofs - Amherst College
• Logic and Proof - Lean
• FORMAL PROOFS - Purdue University
• Language Proof Logic Answer Key Chapter 3