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

# Logic, Proofs - Northwestern University - logic proof calculator with steps

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. 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
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.

#### Pdf INFO

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