a neat proof


Theorem

\displaystyle  \left\{ \begin{array}{ll} \sin nt & n=1,2,\dots,\infty \\ \cos mt & m=0,1,2,\dots,\infty \end{array} \right.

Any two distinct ones are orthogonal on {[-\pi,\pi]}.

Proof: We’ve already known that {\sin nt} and {\cos nt} are orthogonal, because

\displaystyle  \int_{-\pi}^\pi \sin nt \cos nt \mathrm{d}t = -\frac{1}{4n}\int_{-\pi}^{\pi}\sin 2nt\mathrm{d}(2nt)=0.

Let {u_n} and {v_m} be any two of these functions where {m\neq n},

\displaystyle  \int_{-\pi}^\pi u_n''v_m\mathrm{d}t =u_n'v_m\Bigr|_{-\pi}^\pi-\int_{-\pi}^\pi u_n'v_m'\mathrm{d}t.

Since {u_n'v_m\Bigr|_{-\pi}^\pi=0},

\displaystyle  \int_{-\pi}^\pi u_n''v_m\mathrm{d}t=\int_{-\pi}^\pi v_m''u_n\mathrm{d}t.

But we also know {\sin nt} and {\cos nt} satisfy 2nd-order ODE

\displaystyle  u''+n^2u=0

hence,

\displaystyle  \int_{-\pi}^\pi u_n''v_m\mathrm{d}t =-n^2\int_{-\pi}^\pi u_nv_m\mathrm{d}t,

\displaystyle  \int_{-\pi}^\pi v_m''u_n\mathrm{d}t = -m^2\int_{-\pi}^\pi u_nv_m\mathrm{d}t,

and

\displaystyle  -n^2\int_{-\pi}^\pi u_nv_m\mathrm{d}t=-m^2\int_{-\pi}^\pi u_nv_m\mathrm{d}t

Since {m\neq n},

\displaystyle  \int_{-\pi}^\pi u_nv_m\mathrm{d}t=0.

\Box

Advertisements

Trick to memorize Bayes’ theorem

First, we need a partition of the sample space {S}. Let’s say, {B_j}. Bayes’ theorem is used when we know {\mathop{\mathbb P}(B_j)} and {\mathop{\mathbb P}(A|B_j)} for every {j}, and we want to know {\mathop{\mathbb P}(B_i|A)} for some {i}. The word “partition” has two meanings, which is essential for the whole idea to work.

  • {B_j}s cover the whole sample space.
  • {B_j}s are disjoint.

Theorem 1 (Bayes’ theorem)

\displaystyle  \mathop{\mathbb P}(B_i|A)=\frac{\mathop{\mathbb P}(B_i)\mathop{\mathbb P}(A|B_i)}{\sum_{j=1}^k \mathop{\mathbb P}(B_j)\mathop{\mathbb P}(A|B_j)}

The formula seems a total mess at first glance, but if we look harder, we find out the numerator is {\mathop{\mathbb P}(B_iA)} due to the definition of conditional probability and the denominator is just {\mathop{\mathbb P}(A)} due to the law of total probability. Taking one step closer, the numerator {\mathop{\mathbb P}(B_iA)} is one fraction of {A}: {B_iA} relative to {S}, and the denominator {\mathop{\mathbb P}(A)} is the sum of all fractions of {A}{A} itself: {A} relative to {S}. Hence the RHS of the formular is {B_iA} relative to {A} — the conditional probability of {B_i} given {A}.

Theorem 2 (The Conditional Version of Bayes’ Theorem)

\displaystyle  \mathop{\mathbb P}(B_i|AC)=\frac{\mathop{\mathbb P}(B_i|C)\mathop{\mathbb P}(A|B_iC)}{\sum_{j=1}^k \mathop{\mathbb P}(B_j|C)\mathop{\mathbb P}(A|B_jC)}

O.K. Here comes the trick. The whole idea behind Bayes’ theorem is that knowing every piece of {\mathop{\mathbb P}(A|B_j}), and {\mathop{\mathbb P}(B_j)} of course, to determine {\mathop{\mathbb P}(B_j|A)}, kind of like switching the condition and the target event. So, Switch the two events around “{|}” in the probability we want to determine, and write it down in the numerator. (We always multiply the probability of the conditional event to get something — {\mathop{\mathbb P}(B_iA)}). Write {\mathop{\mathbb P}}(whatever on the right of “{|}” you just wrote) in the numerator. Copy the numerator to the denominator, except change {i} to{ j}, and sum it. ({i} is a specific number, and {j} is every possible index of the partition.) And for conditional version of Bayes’ theorem, just plug “{|C}” before each “)” if there is no “{|}” yet in the parenthesis:

It is important to notice that the numerator is one of the terms of the denominator. This is the main reason behind Example 2.3.6. Although the misdiagnosis rate is only 10% for those who actually has the disease, it’s also 10% for the healthy test taker to be misdiagnosed, a large part of the denominator, overwhelming the other part in the denominator as same as the numerator, which is relatively too high because the majority doesn’t has the disease. As a result, the conditional probability is exaggerated when taken for granted.


Logic Homework 1

  1. Classify each of the following five expressions as either an atomic sentence, a negation, a conjunction, a disjunction, a conditional, a biconditional, or not an SC sentence. For each of the expressions that is an SC sentence, give a structure tree:

    a) ¬(P ∨ (Q ∧ ¬R))
    b) (¬P ∨ (Q ∧ ¬R))
    c) ((¬P ∨ Q) ∧ ¬R)
    d) ¬¬(¬¬φ ↔ ¬¬¬¬ψ)
    e) (((A → B) → C) → ((A → C) → C))

    Solution:
    a) negation

    b) disjunction

    c) conjunction

    d) negation

    e) conditional


  2. Give an example of each of the following:

    a) a disjunction both of whose disjuncts are atomic.
    b) a disjunction both of whose disjuncts are conjunctions both of whose
    conjuncts are disjunctions.
    c) a conditional whose antecedent is a biconditional and whose consequent is a
    negated biconditional.

    Solution:
    a) (P ∨ Q)
    b) (((P ∨ Q) ∧ (P ∨ Q)) ∨ ((P ∨ Q) ∧ (P ∨ Q)))
    c) ((P ↔ Q) → ¬(P ↔ Q))


  3. Describe an algorithm that, given an SC sentence as input, determines which of the six categories (atomic, negation, conjunction, disjunction, conditional, or biconditional) it falls into. Explain why your algorithm gives the correct classification of each of the SC sentences from problem 1.

    Solution:

    def identify(s):
        assert type(s) is str
        if s[0] == "!": return s + " is a negation"
        if s[0] != "(": return s + " is a atomic sentence"
        p=0
        i=1
        while i < len(s):
            if s[i] == "(": p += 1
            if s[i] == ")": p -= 1
            if s[i] == "&" and p == 0: return s + " is a conjunction"
            if s[i] == "|" and p == 0: return s + " is a disjuction"
            if s[i] == "-" and p == 0: return s + " is a conditional"
            if s[i] == "+" and p == 0: return s + " is a conditional"
            if s[i] == "=" and p == 0: return s + " is a biconditional"
            if p < 0: return s + " is not a correct SC sentence"
            i += 1
    

  4. A substitution is an operation that replaces each atomic sentence by an SC sentence, making sure that the same replacement is made for all instances of a given atomic sentence. In other work, a substitution is a function s associating SC sentences with SC sentences that meets the following conditions:

    s((φ ∨ ψ)) = (s(φ) ∨ s(ψ))
    s((φ ∧ ψ)) = (s(φ) ∧ s(ψ))
    s((φ → ψ)) = (s(φ) → s(ψ))
    s((φ ↔ ψ)) = (s(φ) ↔ s(ψ))
    s(¬φ) = ¬s(φ)

    Let s be a substitution with s(“P“) = “(PQ),” s(“Q“) = “((PQ) → R),” and s(φ) = φ for φ an atomic sentence other than “P” or “Q“.

    a) What is s(“(PR)”)?
    b) What is s(“(PQ)”)?
    c)What is s(s(“(PR)”))?
    d) Give two distinct SC sentences φ and ψ with s(φ) = s(ψ).

    Solution:
    a) s(“(PR)”)
    = (s(“P“) ∨ s(“R“))
    = “((PQ) ∨ R)”
    b) s(“(PQ)”)
    = (s(“P“) ∨ s(“Q“))
    = “((PQ) ∨ ((PQ) → R))”
    c) s(s(“(PR)”))
    = s(“((PQ) ∨ R)”)
    = (s(“(PQ)”) ∨ s(“R“))
    = “(((PQ) ∨ ((PQ) → R)) ∨ R)”
    d) φ = (PR), ψ = Q
    s(“φ“)
    = s(“(PR)”)
    = (s(“P“) → R)
    = “((PQ) → R)”
    = s(“ψ“)


Review of problem set 1 of mit 18.05

1-5 pg. 27 #7
If 12 balls are thrown at random into 20 boxes, what is the probability that no box will receive more than one ball?

Correct solution:
\#(S)=20^{12}
\#(E)=\frac{20!}{8!}
\textup{Pr}(E)=\frac{P_{20,12}}{20^{12}}

Erroneous solution:
\#(S)=\binom{31}{12}
# of different ways to arrange 12 balls and 19 separators, balls and separators are not distinguishable, unordered.
\#(E)=\binom{20}{12}
# of different ways to choose 12 boxes from 20 to put one ball for each, the order of elements in selection doesn’t matter.
\textup{Pr}(E)=\frac{\binom{31}{12}}{\binom{20}{12}}

Mistake: The Probability assigned to the sample space is not equally probable, hence the sample space is not simple. Situations that same boxes occupied by same number of balls but by different balls are counted only once, which is more likely to happen than all balls are put in a certain box, which is also counted once.

This mistake is just like another one: Tossing 3 coins simultaneously, defining the outcomes to be no heads, one heads, two heads, and three heads.

1-6 pg. 27 #10
A box contains 100 balls, of which r are red. Suppose that the balls are drawn from the box one at a time, at random, without replacement. Determine (a) the probability that the first ball drawn will be red; (b) the probability that the 50th ball drawn will be red; and (c) the probability that the last ball drawn will be red.

Solution:
Ai = {draw red at step i}
think of arranging the balls in 100 spots in a row.
(a)\textup{Pr}(A_1)=\frac{r}{100}
(b)\textup{Pr}(A_{50})
sample space = sequences of length 50.
\#(S) = 100 \times 99 \times \cdots \times 50 = P_{100,50}
\#(A_{50}) = r \times P_{99,49} red on 50. There are 99 balls left, r choices to put red on 50.
P(A_{50}) =	\frac{r}{100}, same as part a.
(c) As shown in part b, the particular draw doesn’t matter, probability is the same.
P(A_{100})=\frac{r}{100}

1-8 pg.34 #16(b)
The United States Senate contains two senators from each of the 50 states. What is the probability that a group of 50 senators selected at ramdom will contain on senator from each state?

Solution:
\#(S)=\binom{100}{50}
\#(E)=2^{50}
2 choices in selecting from the 1st states, 2 from the next…

or
\#(E)=\frac{100!!}{50!}
100 choices in selecting the 1st person, 98 choices in selecting the next…and to eliminate the identical group but in different order when selected, divide by 50!.
actually
2^{50}=\frac{100!!}{50!}
and
\textup{Pr}(E)=\frac{20^{50}}{\binom{100}{50}}=\frac{100!!}{P_{100,50}}

1-11 If you throw r white balls into n boxes, r ≥ n, what is the number of distinguishable configurations in which no box remains empty?

Solution:
First of all, put 1 ball in each box from the beginning. r-n balls remain to be distributed in n boxes. (Use the ball/separator model)
\#=\binom{n+(r-n)-1}{r-n}=\binom{r-1}{r-n}

However, figuring out the probability that no box remains empty is not that easy. Because if we use the ball/separator model to find the number of elements in sample space, the sample space would not be simple. And if we assume the balls are numbered, the outcomes in the event would be hard to determine. A solution involving independency and the probability of the union of finite number of events is available at pg. 63 – the collector’s problem.

1-12 Given thirty people find the probability that among the twelve months there are six containing two birthdays and six containing three.

Solution:
30 people, 12 months.
Pr(6 months with 3 birthdays, 6 months with 2 birthdays)
\#(S) = 12^{30}
Need to choose the 6 months with 3 or 2 birthdays, then the multinomial coefficient:
\#(\textrm{possibilities})=\binom{12}{6} \binom{30}{3,3,3,3,3,3,2,2,2,2,2,2}


Logic Ⅰ (lec8~12)

Definition.A set of sentences Ω is a complete story just in case it satisfies the following five conditions, for any φ and ψ:
a) (φ ∧ ψ) ∈ Ω iff φ ∈ Ω and ψ ∈ Ω.
b) (φ ∨ ψ) ∈ Ω iff φ ∈ Ω or ψ ∈ Ω (or both).
c) (φ → ψ) ∈ Ω iff φ ∉ Ω or ψ ∈ Ω (or both).
d) (φ ↔ ψ) ∈ Ω iff φ and ψ are both in Ω or neither of them is.
e) ¬φ ∈ Ω iff φ ∉ Ω.

Lemma. A set of sentences Ω is a complete story iff it satisfies these two conditions:
1) Every finite subset of Ω is consistent.
2) For each sentence φ, either φ or ¬φ is an element of Ω.

Lemma. Suppose that every finite subset of ∆ is consistent. Take a sentence ψ. Then either every finite subset of ∆ ∪ {ψ} is consistent or every finite subset of ∆ ∪ {¬ψ} is consistent.

Compactness Theorem. A set Γ of SC sentences is consistent if and only if every finite subset of Γ is consistent.

Corollary. If φ is a logical consequence of a set of sentences ∆, then φ is a logical consequence of some finite subset of ∆.

Soundness and Completeness Theorem. A sentence χ is a logical consequence of a set of sentences Γ if and only if there is a derivation by which χ is derived from a premiss set that is included in Γ.

Weak Completeness Theorem. Every valid SC sentence is an SC theorem.

Basic Rules of Deduction

Premiss Introduction Rule (PI).You may write down any sentence you like if you take the sentence as its own premiss set.

Conditional Proof Rule (CP). If you have derived ψ with premiss set Γ, you may write (φ → ψ) with premiss set Γ ~ {φ}

Modus Ponens Rule (MP). If you have derived φ with premiss set Γ and (φ → ψ) with premiss set ∆, you may write ψ with premiss set Γ ∪ ∆.

Modus Tollens Rule (MT). If you have derived ψ with premiss set Γ and (¬φ → ¬ψ) with premiss set ∆, you may write φ with premiss set Γ ∪ ∆.

Rule for Definition of Connectives (DC). You may write an instance of any of the following six schemata with the empty premiss set:

((φ ∨ ψ) → (¬φ → ψ))
((¬φ → ψ) → (φ ∨ ψ))
((φ ∧ ψ) → ¬(φ → ¬ψ))
(¬(φ → ¬ψ) → (φ ∧ ψ))
((φ ↔ ψ) → ((φ → ψ) ∧ (ψ → φ)))
(((φ → ψ) ∧ (ψ → φ)) → (φ ↔ ψ))

Derived Rules

Theorem Substitution Derived Rule (TH). If you have already proved φ from the empty set, you may, at any time in any derivation, write down any substitution instance of φ, again with the empty premiss set.

Derived Rule for the Substitution of Equivalents (SE). Suppose that φ has been derived from the premiss set Γ, that (χ ↔ θ) has been derived with premiss set ∆, and that ψ has been obtained from φ either by replacing χ with θ or by replacing θ with χ. Then you may derive ψ with premiss set Γ ∪ ∆.

Derived Rule for Biconditional Introduction (BI). If you have derived both (φ → ψ) and (ψ → φ), you may write (φ ↔ ψ), taking as premiss set the union of the premiss sets of the two conditionals.

SC Theorems We Have Proved Thus Far

TH1 (¬¬P → P) Double negation elimination
TH2 (Q → (P → Q))
TH3 ((P → Q) → ((Q → R) → (P → R))) Principle of the syllogism
TH4 (((P → (Q → R)) → (Q → (P → R)))
TH5 (P → ¬¬P) Double negation introduction
TH6 (¬P → (P → Q)) Law of Duns Scotus
TH7 ((¬P → P) → P) Law of Clavius
TH8 (((P → Q) → R) → ((P → R) → R)))
TH9 ((P → Q) → ((¬P → Q) → Q))
TH10 (P → (P ∨ Q)) A disjunction introduction principle
TH11 (Q → (P ∨ Q)) A disjunction introduction principle
TH12 ((P → R) → ((Q → R) → ((P ∨ Q) → R))) Principle of disjunctive syllogism
TH13 ((P ∧ Q) → P) A conjunction elimination principle
TH14 ((P ∧ Q) → Q) A conjunction elimination principle
TH15 (P → (Q → (P ∧ Q))) Conjunction introduction principle
TH16 ((P → Q) → ((Q → P) → (P ↔ Q)))
TH17 ((P ↔ Q) → (P → Q))
TH18 ((P ↔ Q) → (Q → P))
TH19 ((P → Q) → (¬Q → ¬P))
TH20 ((¬Q → ¬P) → (P → Q))
TH21 ((P → Q) ↔ (¬Q → ¬P)) Principle of contraposition
TH22 (¬(P ∧ Q) ↔ (¬P ∨ ¬Q)) One of de Morgan’s laws
TH23 (P → P)
TH24 (P ↔ P)
TH25 (P ↔ ¬¬P)
TH26 ((P ∨ Q) ↔ (¬P → Q))
TH27 ((P ∧ Q) ↔ ¬(P → ¬Q))
TH28 ((P ↔ Q) ↔ ¬(P → ¬Q))
TH29 ((P → (Q → R)) → ((P ∧ Q) → R))
TH30 (((P ∧ Q) → R) → (P → (Q → R)))
TH31 ((P → (Q → R)) ↔ ((P ∧ Q) → R))
TH32 (¬(P ∨ Q) ↔ (¬ P ∧ ¬Q)) One of de Morgan’s laws
TH33 ((P ∨ Q) ↔ (Q ∨ P)) Commutative law for “∨”
TH34 ((P ∨ (Q ∨ R)) ↔ ((P ∨ Q) ∨ R)) Associative law for “∨”
TH35 ((P ∨ P) → P)
TH36 ((P ∨ P) ↔ P) Idempotence for “∨”
TH37 ((P ∧ Q) ↔ (Q ∧ P)) Commutative law for “∧”
TH38 ((P ∧ (Q ∧ R)) ↔ ((P ∧ Q) ∧ R)) Associative law for “∧”
TH39 ((P ∧ P) ↔ P) Idempotence for “∧”
TH40 ((P ∧ (Q ∨ R)) → ((P ∧ Q) ∨ (P ∧ R)))
TH41 (((P ∧ Q) ∨ (P ∧ R)) → (P ∧ (Q ∨ R)))
TH42 (((P ∧ (Q ∨ R)) ↔ ((P ∧ Q) ∨ (P ∧ R))) Distributive law
TH43 ((P ∨ (Q ∧ R)) → ((P ∨ Q) ∧ (P ∨ R))) Another distributive law

Logic Homework 2

Subject 24.241. Logic I. Homework due Thursday, September 29.

1.For this problem, let N be the set of natural numbers (nonnegative integers), let E be the set of even natural numbers, let P be the set of primes (integers>1 that aren’t divisible by any numbers other than themselves and one), and let S be the set of integers greater than 1 and less than 10.
a) List the members of S ~ P.
{4, 6, 8, 9}

b) List the members of S ~ (P ∪ E)
{9}

c) List the members of P ∩ E.
{2}

d) List the members of (S ~ P) ~ E.
{9}

e) List the members of S ~ (P ~ E).
{2, 4, 6, 8, 9}

2.For this problem, let I be {Mercury,Venus, Earth, Mars), and let C = {Spock,McCoy}.
a) List the functions from I to C, indicating which are one-one and which are onto.
There should be 24=16 functions. Due to pigeonhole theory, none of them is one-one and 14 of them are onto.
{<Mercury, Spock>, <Venus, Spock>, <Earth, Spock>, <Mars, Spock>}
{<Mercury, Spock>, <Venus, Spock>, <Earth, Spock>, <Mars, McCoy>} onto
{<Mercury, Spock>, <Venus, Spock>, <Earth, McCoy>, <Mars, Spock>} onto
{<Mercury, Spock>, <Venus, Spock>, <Earth, McCoy>, <Mars, McCoy>} onto
{<Mercury, Spock>, <Venus, McCoy>, <Earth, Spock>, <Mars, Spock>} onto
{<Mercury, Spock>, <Venus, McCoy>, <Earth, Spock>, <Mars, McCoy>} onto
{<Mercury, Spock>, <Venus, McCoy>, <Earth, McCoy>, <Mars, Spock>} onto
{<Mercury, Spock>, <Venus, McCoy>, <Earth, McCoy>, <Mars, McCoy>} onto
{<Mercury, McCoy>, <Venus, Spock>, <Earth, Spock>, <Mars, Spock>} onto
{<Mercury, McCoy>, <Venus, Spock>, <Earth, Spock>, <Mars, Spock>} onto
{<Mercury, McCoy>, <Venus, Spock>, <Earth, Spock>, <Mars, McCoy>} onto
{<Mercury, McCoy>, <Venus, Spock>, <Earth, McCoy>, <Mars, Spock>} onto
{<Mercury, McCoy>, <Venus, Spock>, <Earth, McCoy>, <Mars, McCoy>} onto
{<Mercury, McCoy>, <Venus, McCoy>, <Earth, Spock>, <Mars, Spock>} onto
{<Mercury, McCoy>, <Venus, McCoy>, <Earth, Spock>, <Mars, McCoy>} onto
{<Mercury, McCoy>, <Venus, McCoy>, <Earth, McCoy>, <Mars, Spock>} onto
{<Mercury, McCoy>, <Venus, McCoy>, <Earth, McCoy>, <Mars, McCoy>}

b) How many functions are there from I to I. of these how many are one-one? Onto? Both?
There are 44=256 functions.
4!=24 of them are both one-one and onto.

3.Use the method of truth table to identifl each of the following sentences as valid, inconsistent, or neither.
a) (((P ↔ (Q ↔ R)) ↔ ((P ↔ Q) ↔ ¬R)))

P Q R (((P (Q R)) ((P Q) ¬ R)))
1 1 1 1 1 1 1 1 0 1 1 1 0 0 1
1 1 0 1 0 1 0 0 0 1 1 1 1 1 0
1 0 1 1 0 0 0 1 0 1 0 0 1 0 1
1 0 0 1 1 0 1 0 0 1 0 0 0 1 0
0 1 1 0 0 1 1 1 0 0 0 1 1 0 1
0 1 0 0 1 1 0 0 0 0 0 1 0 1 0
0 0 1 0 1 0 0 1 0 0 1 0 0 0 1
0 0 0 0 0 0 1 0 0 0 1 0 1 1 0

inconsistent

b) (((P → Q) → R) → ((P → R) → R))

P Q R (((P Q) R) ((P R) R))
1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 0 0 1 1 0 0 1 0
1 0 1 1 0 0 1 1 1 1 1 1 1 1
1 0 0 1 0 0 1 0 1 1 0 0 1 0
0 1 1 0 1 1 1 1 1 0 1 1 1 1
0 1 0 0 1 1 0 0 1 0 1 0 0 0
0 0 1 0 1 0 1 1 1 0 1 1 1 1
0 0 0 0 1 0 0 0 1 0 1 0 0 0

valid

c) (((P → (Q ∨ R)) ∨ ((P → Q) ∨ R))

P Q R (((P (Q R)) ((P Q) R))
1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 0 1 1 1 1 1 0
1 0 1 1 1 0 1 1 1 1 0 0 1 1
1 0 0 1 1 0 1 0 1 1 0 0 0 0
0 1 1 0 1 1 1 1 1 0 1 1 1 1
0 1 0 0 1 1 1 0 1 0 1 1 1 0
0 0 1 0 1 0 1 1 1 0 1 0 1 1
0 0 0 0 1 0 0 0 1 0 1 0 1 0

valid

4.For each of the following categories, either give an example or explain why there can’t be any example:
a) A tautological conditional whose antecedent is tautological.
((A ∨ ¬A) → (A ∨ ¬A))

b) An inconsistent conditional whose antecedent is inconsistent.
Can’t. Because if antecedent is inconsistent, the conditional is tautological.

c) A tautological disjunction neither of whose disjuncts are tautological.
A ∨ ¬A

d) A tautological conjunction neither of whose conjuncts are tautological.
Can’t. SC Theorem 4. A conjunction is tautological iff both its conjuncts are tautological.

e) An inconsistent sentence with no negation signs.
Can’t. Under the N.T.A. that every atomic sentences are true, every conjunction, disjunction, conditional and biconditional will also be true. Hence the sentence can’t be inconsistent without negation.


Logic Ⅰ (lec1~7)

Definition. A truth assignment for a language for the sentential calculus is a function that assigns a number, either 0 or 1, to each sentence.

Definition. A truth assignment 𝕴 for a language for the sentential calculus is a normal truth assignment (N.T.A.) just in case it satisfies the following conditions:

A conjunction is assigned the value 1 if and only if both its conjuncts are assigned 1.
A disjunction is assigned 1 if and only if one or both disjuncts are assigned 1.
A conditional is assigned 1 if and only if either its antecedent is assigned 0 or its consequent is assigned 1 (or both).
A biconditional is assigned 1 if and only if its components are both assigned the same value.
A negation is assigned 1 if and only if the negatum is assigned 1.

Definition. A sentence is said to be true under a N.T.A. if and only if it’s assigned the value 1 by the N.T.A. A sentence that’s assigned 0 by the N.T.A. is false under the N.T.A.

Definition. An sentence is a tautology (or is valid or necessary) if and only if it is true under every N.T.A. A sentence is a contradiction (or is inconsistent or impossible) if and only if it is false under every . A sentence is indeterminate (or contingent or mixed) if and only if it is true under some N.T.A.s and false under others.

SC Theorem 1. An sentence is a tautology if and only if its negation is a contradiction.

SC Theorem 2. An SC sentence is contradictory iff its negation is a tautology.

SC Theorem 3. An SC sentence is indeterminate iff its negation is indeterminate.

SC Theorem 4. A conjunction is tautological iff both its conjuncts are tautological.

SC Theorem 5. For any SC sentences φ and ψ, if φ is a contradiction or ψ is a contradiction, then (φ ∧ ψ) is a contradiction.

SC Theorem 6. A conditional is contradictory iff its antecedent is a tautology and its consequent is a contradiction.

Definition. Two sentences are logically equivalent iff they are true under precisely the same N.T.A.s.

SC Theorem 7. Two SC sentences φ and ψ are logically equivalent iff the biconditional (φ ↔ ψ) is a tautology.

SC Theorem 8 (Augustus de Morgan). ¬(φ ∨ ψ) is logically equivalent to (¬φ ∧ ¬ψ).

SC Theorem 9 (also due to de Morgan). ¬(φ ∧ ψ) is logically equivalent to (¬φ ∨ ¬ψ).

SC Theorem 10. Let 𝕴 be a N.T.A. and let φ, ψ, χ, and θ be SC sentences such that 𝕴(φ) = 𝕴(ψ) and such that χ and θ are just alike except that some occurrences of φ as a subsentence of χ have been replace by occurrences of ψ as subsentences of θ. The 𝕴(χ) = 𝕴(θ).

SC Theorem 11. If the SC sentences φ and ψ are logically equivalent and if χ and θ are just alike except that some occurrences of φ as a subsentence of χ have been replaced by occurrences of ψ as a subsentence of θ, then χ and θ are logically equivalent.

Definition. An SC sentence implies (or entails) a sentence ψ iff there is no N.T.A. under which φ is true and ψ is false. In other words, φ implies ψ iff ψ is true under every N.T.A. under which φ is true.

SC Theorem 12. For any sentences φ and ψ, φ implies ψ iff the conditional (φ → ψ) is a tautology.

SC Theorem 13. A contradiction implies every sentence.

SC Theorem 14. A tautology is implied by every sentence.

SC Theorem 15. Two sentences are logically equivalent iff each implies the other.

Definition. An SC argument is a finite sequence of SC sentences. The last member of the sequence is the conclusion and the earlier members are the premisses. The argument is valid iff there is no N.T.A. under which all the premisses are true and the conclusion is false.

SC Theorem 16. An SC argument

φ1
φ2

φn
∴ψ

is valid iff the conjunction (φ1 ∧ (φ2 ∧ … ∧ φn)…) implies ψ.

SC Theorem 17. An SC argument

φ1
φ2

φn
∴ψ

is valid iff the conditional ((φ1 ∧ (φ2 ∧ … ∧ φn)…) → ψ) is a tautology.

Definition. A sentence φ is a logical consequence of a set of sentences Γ iff there is no N.T.A. which assigns the value T to all the members of Γ and assigns F to φ.

Definition. A set of sentences is consistent iff there is at least one N.T.A. by which all its members are assigned T.

Simplest Example Lemma. If there is an SC sentence with a given property, then there is a simplest SC sentence with the property. More precisely, there is an SC sentence having the property such that no proper subsentence has the property.

Extension Theorem. Any function assigning a numerical value, either 0 or 1, to every atomic sentence can be extended to a normal truth assignment in a unique way.

No-Conflict Lemma. If J and K are normal extensions of H and φ is in the domain of both of them, then J(φ) = K(φ).

Definition.substitution is a function s associating SC sentences with SC sentences that meets the following conditions:

s((φ ∨ ψ)) = (s(φ) ∨ s(ψ))
s((φ ∧ ψ)) = (s(φ) ∧ s(ψ))
s((φ → ψ)) = (s(φ) → s(ψ))
s((φ ↔ ψ)) = (s(φ) ↔ s(ψ))
s(¬φ)= ¬s(φ)

Definition. If φ is a sentence and s is a substitution, then s(φ) is said to be a substitution instance of φ.

Substitution Theorem 1. Any substitution instance of a tautology is a tautology. Any substitution instance of a contradiction is a contradiction.

Substitution Theorem 2. Let s be a substitution. If φ implies ψ, then s(φ) implies s(ψ). If φ and ψ are logically equivalent, s(φ) and s(ψ) are logically equivalent. If φ is a logical consequence of Γ, then s(φ) is a logical consequence of {s(γ): γ ∈ Γ}.

Substitution Theorem 3. A sentence φ is consistent if and only if some substitution instance of φ is tautological.

Substitution Theorem 4. A sentence φ is tautological iff every substitution instance of φ is tautological iff every substitution instance of φ is consistent. A sentence ψ is contradictory iff every substitution instance of ψ is contradictory iff every substitution instance of ψ is invalid.

Substitution Theorem 5. Let φ and ψ be sentences whose only connectives are “∧,” “∨,” and “¬.” Then if φ implies ψ, ψDual implies φDual. If φ is logically equivalent to ψ, φDual is logically equivalent to ψDual.