Term
|
Definition
A sentence φ and a sentence ψ are logically equivalent if and only if the sentence (φ ⇔ ψ) is valid. |
|
|
Term
|
Definition
a sentence φ logically entails a sentence ψ (written φ ⊨ ψ) if and only if every truth assignment that satisfies φ also satisfies ψ. More generally, a set of sentences Δ logically entails a sentence ψ (written Δ ⊨ ψ) if and only if every truth assignment that satisfies all of the sentences in Δ also satisfies ψ. |
|
|
Term
|
Definition
A proof is sufficient evidence or a sufficient argument for the truth of a proposition |
|
|
Term
|
Definition
is reasoning from the particular to the general |
|
|
Term
|
Definition
is reasoning from effects to possible causes |
|
|
Term
|
Definition
reasoning in which we infer a conclusion based on similarity of two situations |
|
|
Term
|
Definition
is the logic of propositions. Symbols in the language represent "conditions" in the world, and complex sentences in the language express interrelationships among these conditions. The primary operators are Boolean connectives, such as and, or, and not. |
|
|
Term
|
Definition
expands upon Propositional Logic by providing a means for explicitly talking about individual objects and their interrelationships (not just monolithic conditions). In order to do so, we expand our language to include object constants and relation constants, variables and quantifiers. |
|
|
Term
|
Definition
takes us one step further by providing a means for describing worlds with infinitely many objects. The resulting logic is much more powerful than Propositional Logic and Relational Logic. Unfortunately, many of the nice computational properties of the first two logics are lost as a result |
|
|
Term
|
Definition
the study of information encoded in the form of logical sentences. Each logical sentence divides the set of all possible world into two subsets the set of worlds in which the sentence is true and the set of worlds in which the set of sentences is false. |
|
|
Term
|
Definition
in Propositional Logic are often called proposition constants or, sometimes, logical constants. |
|
|
Term
|
Definition
formed from simpler sentences and express relationships among the constituent sentences. There are five types of compound sentences, viz. negations, conjunctions, disjunctions, implications, and biconditionals. |
|
|
Term
|
Definition
consists of the negation operator ¬ and an arbitrary sentence, called the target.
For example, given the sentence p, we can form the negation of p as shown below.
(¬p)
If the truth value of a sentence is true, the truth value of its negation is false. If the truth value of a sentence is false, the truth value of its negation is true. |
|
|
Term
|
Definition
a sequence of sentences separated by occurrences of the ∧ operator and enclosed in parentheses, as shown below. The constituent sentences are called conjuncts.
For example, we can form the conjunction of p and q as follows.
(p ∧ q)
|
|
|
Term
|
Definition
a sequence of sentences separated by occurrences of the ∨ operator and enclosed in parentheses. The constituent sentences are called disjuncts.
For example, we can form the disjunction of p and q as follows.
(p ∨ q)
|
|
|
Term
|
Definition
consists of a pair of sentences separated by the ⇒ operator and enclosed in parentheses. The sentence to the left of the operator is called the antecedent, and the sentence to the right is called the consequent.
The implication of p and q is shown below.
(p ⇒ q)
|
|
|
Term
|
Definition
a combination of an implication and a reverse implication.
For example, we can express the biconditional of p and q as shown below.
(p ⇔ q)
|
|
|
Term
|
Definition
The following table gives a hierarchy of precedences for our operators. The ¬ operator has higher precedence than ∧; ∧ has higher precedence than ∨; and ∨ has higher precedence than ⇒ and ⇔.
¬ ∧ ∨ ⇒ ⇔ |
|
|
Term
|
Definition
a set of proposition constants |
|
|
Term
|
Definition
the set of all propositional sentences that can be formed from a propositional vocabulary. |
|
|
Term
|
Definition
a truth assignment for a propositional vocabulary is a function assigning a truth value to each of the proposition constants of the vocabulary.
We say that a truth assignment satisfies a sentence if and only if the sentence is true under that truth assignment. We say that a truth assignment falsifies a sentence if and only if the sentence is false under that truth assignment. A truth assignment satisfies a set of sentences if and only if it satisfies every sentence in the set. A truth assignment falsifies a set of sentences if and only if it falsifies at least one sentence in the set. |
|
|
Term
|
Definition
In propositional logic, material implication is a valid rule of replacement that allows for a conditional statement to be replaced by a disjunction in which the antecedent is negated. The rule states that P implies Q is logically equivalent to not-P or Q and can replace each other in logical proofs.
[image]
|
|
|
Term
|
Definition
is the process of determining the truth values of compound sentences given a truth assignment for the truth values of proposition constants |
|
|
Term
|
Definition
is the opposite of evaluation. We begin with one or more compound sentences and try to figure out which truth assignments satisfy those sentences. |
|
|
Term
|
Definition
A truth table for a propositional language is a table showing all of the possible truth assignments for the proposition constants in the language. The columns of the table correspond to the proposition constants of the language, and the rows correspond to different truth assignments for those constants. |
|
|
Term
|
Definition
A sentence is valid if and only if it is satisfied by every truth assignment. For example, the sentence (p ∨ ¬p) is valid. If a truth assignment makes p true, then the first disjunct is true and the disjunction as a whole true. If a truth assignment makes p false, then the second disjunct is true and the disjunction as a whole is true. |
|
|
Term
|
Definition
A sentence is unsatisfiable if and only if it is not satisfied by any truth assignment. For example, the sentence (p ∧ ¬p) is unsatisfiable. No matter what truth assignment we take, the sentence is always false. The argument is analogous to the argument in the preceding paragraph. |
|
|
Term
|
Definition
a sentence is contingent if and only if there is some truth assignment that satisfies it and some truth assignment that falsifies it. For example, the sentence (p ∧ q) is contingent. If p and q are both true, it is true. If p and q are both false, it is false. |
|
|
Term
|
Definition
a sentence is satisfiable if and only if it is valid or contingent. In other words the sentence is satisfied by at least one truth assignment. |
|
|
Term
|
Definition
a sentence is falsifiable if and only if it is unsatisfiable or contingent. In other words, the sentence is falsified by at least one truth assignment. |
|
|
Term
|
Definition
A sentence φ is consistent with a sentence ψ if and only if there is a truth assignment that satisfies both φ and ψ. A sentence ψ is consistent with a set of sentences Δ if and only if there is a truth assignment that satisfies both Δ and ψ. |
|
|
Term
|
Definition
A sentence φ logically entails a sentence ψ if and only if (φ ⇒ ψ) is valid. More generally, a finite set of sentences {φ1, ... , φn} logically entails φ if and only if the compound sentence (φ1 ∧ ... ∧ φn ⇒ φ) is valid. |
|
|
Term
|
Definition
Unsatisfiability Theorem: A set Δ of sentences logically entails a sentence φ if and only if the set of sentences Δ ∪ {¬φ} is unsatisfiable.
Suppose that Δ logically entails φ. If a truth assignment satisfies Δ, then it must also satisfy φ. But then it cannot satisfy ¬φ. Therefore, Δ ∪ {¬φ} is unsatisfiable. Suppose that Δ∪{¬φ} is unsatisfiable. Then every truth assignment that satisfies Δ must fail to satisfy ¬φ, i.e. it must satisfy φ. Therefore, Δ must logically entail φ. |
|
|
Term
|
Definition
A sentence φ is logically consistent with a sentence ψ if and only if the sentence (φ ∧ ψ) is satisfiable. More generally, a sentence φ is logically consistent with a finite set of sentences {φ1, ... , φn} if and only if the compound sentence (φ1 ∧ ... ∧ φn ∧ φ) is satisfiable. |
|
|