Questions about truth tables, conjunctive and disjunctive normal forms, negation, and implication of unquantified propositions would fit very nicely under this tag. Questions about other kind of logics should be tagged with [logic] instead.

learn more… | top users | synonyms (1)

41
votes
17answers
3k views

In classical logic, why is$ (p\Rightarrow q)$ True if both p and q are False?

I am studying entailment in classical first-order logic. The Truth Table we have been presented with for the statement $(p \Rightarrow q)\;$ (a.k.a. '$p$ implies $q$') is: ...
10
votes
8answers
9k views

Not understanding this row of truth table for logical implication

Provided we have this truth table where "$p\implies q$" means "if $p$ then $q$": $$\begin{array}{|c|c|c|} \hline p&q&p\implies q\\ \hline T&T&T\\ T&F&F\\ F&T&T\\ ...
4
votes
4answers
5k views

What is the name of the logical puzzle, where one always lies and another always tells the truth?

So i was solving exercises in propositional logic lately and stumbled upon a puzzle, that goes like this: Each inhabitant of a remote village always tells the truth or always lies. A villager will ...
6
votes
4answers
396 views

Equivalence of $a \rightarrow b$ and $\lnot a \vee b$

Is there a proof for the logical equivalence of $a \rightarrow b$ and $\lnot a \vee b$?
5
votes
3answers
295 views

How to prove or statements

How do I prove statements of the following types: $A \text{ or } B \implies$ C $A \implies B \text{ or } C$ I don't know how to go about proving statements like this when they have "or". Can ...
15
votes
8answers
2k views

Assumed True until proven False. The Curious Case of the Vacuous Truth

Given two statements, $P$ and $Q$, and the logical connective, $\implies$, the truth table for $P \implies Q$ is: $$\begin{array}{ c | c || c | } P & Q & P\Rightarrow Q \\ \hline \text T ...
1
vote
2answers
63 views

Prove $\;\big((p\rightarrow q) \lor (p \rightarrow r)\big) \rightarrow (q\lor r)\equiv p \lor q \lor r$ without use of a truth table.

Without using the truth table, I need to prove: $$\big((p\rightarrow q) \lor (p \rightarrow r)\big) \rightarrow (q\lor r)\equiv p \lor r \lor q$$ Up until now, we've been using truth-tables to ...
12
votes
2answers
1k views

Do De Morgan's laws hold in propositional intuitionistic logic?

In Wikipedia page on intuitionistic logic, it is stated that excluded middle and double negation elimination are not axioms. Does this mean that De Morgan's laws, stated $$ \lnot (p \land q) \iff ...
5
votes
4answers
639 views

What is a constructive proof of $\lnot\lnot(P\vee\lnot P)$?

Glivenko's theorem says that $\lnot\lnot P$ is a theorem of intuitionistic logic whenever $P$ is a theorem of classical logic. Is it closely related to the so-called Gödel–Gentzen negative translation ...
7
votes
5answers
1k views

Help to understand material implication

This question comes from from my algebra paper: $(p \rightarrow q)$ is logically equivalent to ... (then four options are given). The module states that the correct option is $(\sim p \lor q)$. ...
4
votes
3answers
390 views

Natural Deduction Tautology

I'm trying to prove the following tautologies: \begin{align} & ⊢ (A \to (B \to A)) \\ & ⊢ ((A \to B) \to A) \to A \end{align} For the first one, what I did was: $A$ assumption $B$ ...
2
votes
1answer
236 views

How do I Prove the Theorems Needed for “The Deduction Meta-Theorem” from CδCpqCpδq?

I use Polish notation. δ stands for a variable function (or functor) of one argument. A section of Lukasiewicz's book on Aristotle's syllogistic from the modern point of view reads: "I should like ...
1
vote
1answer
86 views

How to prove that $P \rightarrow Q$ is equivalent with $\neg P \lor Q $?

In my book about Logic, which is called 'Language, Proof and Logic', by the way, there is explained that the conditional $ P \rightarrow Q $ is equivalent with $\neg P \lor Q$. There is another ...
1
vote
1answer
280 views

How to prove Lemma 2.12 of Mendelson without Deduction Theorem

My question refers to Bourbaki's axiom system in Nicolas Bourbaki, Théorie des ensembles (1970). [page I.25] : $(P \lor P) \supset P$ --- (Taut) $Q \supset (P \lor Q)$ --- (Add) $(P \lor Q) ...
1
vote
1answer
62 views

How to find if a valuation satisfies a statement?

I'm working on a task which i'm a bit stuck at. I need to decide whether the statements are true or fale. F stands for the statement logical formulas, and also if the claim is true I need to give a ...
0
votes
1answer
92 views

How make equivalent transformations?

Please, help me make equivalent transformations with this formula (A∨C→B)(A→C)(¬B→¬A∧C)(¬A→(C→B))(B→¬C→¬A). Thanks.
4
votes
2answers
353 views

How Many Theorems (Tautologies) Exist of 5, 6, 7, 8, and 9 Letters?

Suppose we only have the material conditional C and logical negation N for a system of propositional calculus, with only variables and no constants in any formula. Suppose that formulas like Cpq ...
6
votes
4answers
2k views

Express logic puzzles with proposition calculus notation

I’m trying to solve a logic puzzle that goes like this: The police have three suspects for the murder of Mr. Cooper: Mr. Smith, Mr. Jones, and Mr. Williams. Smith, Jones, and Williams each declare ...
4
votes
7answers
301 views

Conditional Statements: “only if”

For some reason, be it some bad habit or something else, I can not understand why the statement "p only if q" would translate into p implies q. For instance, I have the statement "Samir will attend ...
2
votes
1answer
76 views

proving $ (A \rightarrow B \vee C )\rightarrow((A\rightarrow B) \vee (A\rightarrow C))$

I'm looking for a way to prow $ (A \rightarrow B \vee C )\rightarrow((A\rightarrow B) \vee (A\rightarrow C))$ from the following axioms and rules $$\vdash A \rightarrow A$$ $$\vdash A \wedge B ...
0
votes
1answer
57 views

Does $\neg(x > y)$ imply that $y \geq x$?

Given any arbitrary binary relation $\geq$ defined on some set $S$, we define a new binary relation $>$ on $S$ by: $$ x > y \quad\text{iff}\quad (x \geq y) \wedge \neg(y \geq x) $$ In accordance ...
8
votes
3answers
708 views

Why Peirce's law implies law of excluded middle?

Why if in a formal system the Peirce's law $((P\rightarrow Q)\rightarrow P) \rightarrow P$ is true, the law of excluded middle $P \lor \neg P$ is true too?
8
votes
2answers
13k views

How to convert to conjunctive normal form?

If i have a formula: $((a \wedge b) \vee (q \wedge r )) \vee z$, am I right in thinking the CNF for this formula would be $(a\vee q \vee r \vee z) \wedge (b \vee q \vee r \vee z) $? Or is there some ...
3
votes
2answers
102 views

Why $¬¬\bot \not\in PROP$?

I'm reading Dalen's Logic and Structure. He gives the definition of the set $PROP$: Definition $\bf2.1.2$ The set $PROP$ of propositions is the smallest set $X$ with the properties ...
3
votes
5answers
587 views

Intuition of implication in propositional logic

So, in all the books on propositional logic, I feel unsatisfied with the "intuition" about the meaning of the implication connective. I completely understand how the mechanics work via truth tables, ...
2
votes
3answers
197 views

Logical Equivalence and Corresponding English Statements

Consider the statement, "If it is Tuesday, then it is raining"; in propositional logic, the statement would read as, "$p \implies q$." Now, in accordance with the rules and definitions prescribed in ...
1
vote
1answer
86 views

In Fitch, is a symbol not in a specified language automatically free?

In Fitch proofs where no language has been specified, we (at least seem to) treat lines that have the form $$p(x)$$ to mean that $x$ "can be anything". That is they are equivalent to $$\forall ...
4
votes
3answers
159 views

A question about Implicational Propositional Calculus

My question is motivated by a previous post about Implicational calculus Having showed that Mendelson (A1) and (A2) axioms plus Peirce's law are a complete axiom set for implicational fragment of ...
3
votes
5answers
832 views

Tautology, Contradiction, or a satisfiable equation? Confusion about implication.

I'm having some trouble with a homework question. I have the following $ P \rightarrow \neg P$ This looks like a contradiction to me. This should never be true! Yet, if I transform it using $p ...
2
votes
2answers
126 views

How can the completeness of Hilbert's axioms be proven?

How can one prove that every propositional tautology, expressed with the connectives '$\neg$' and '$\rightarrow$', can be proved with the axioms below? (P0. $\phi \to \phi$) P1. $\phi \to \left( ...
2
votes
6answers
111 views

Showing that $\lnot Q \lor (\lnot Q \land R) = \lnot Q$ without a truth table

I've done a truth table after reducing it to this and it seems to be equal to $\neg Q$: $$\lnot Q \lor (\lnot Q \land R) = \lnot Q$$ But when I try to show it without a truth table (with just ...
2
votes
2answers
2k views

Every sentence in propositional logic can be written in Conjunctive Normal Form

While reading through Artificial Intelligence: A Modern Approach by Stuart Russell and Peter Norvig, I came upon the following question: Any propositional logic sentence is logically equivalent to ...
1
vote
2answers
88 views

Deriving $\neg R$ from $\{R↔(R∨(P∧¬P)), R↔¬P, ¬P→(P↔(Q→Q)), P→Q\}$

Give a derivation of $\neg R$ from the following premises: $$\{R\leftrightarrow(R\lor(P\land \neg P)), R\leftrightarrow\neg P, \neg P\to(P\leftrightarrow(Q\to Q)), P\to Q\}$$ using the ...
0
votes
3answers
131 views

Can Hilbert (style) prove my tautology?

Can Hilbert (style) axioms prove the following tautology? $$A\wedge(C\rightarrow B)\oplus(A\wedge B\leftrightarrow C)\rightarrow(C\rightarrow(A\rightarrow B))\qquad\text{algebraic style} $$$$ ...
20
votes
4answers
479 views

Associativity of $\iff$

In this answer, user18921 wrote that the $\iff$ operation is associative, in the sense that $(A\iff B)\iff C$ $A\iff (B\iff C)$ are equivalent statements. One can brute-force a proof fairly ...
16
votes
5answers
522 views

If both $P$ and $Q$ are true , how can I tell that $P$ implies $Q$?

I am trying to understand the fundamentals of mathematical logic in order to be able to study discrete mathematics and computer science soon. I have a big problem understanding Implication. I ...
6
votes
5answers
194 views

Is a proposition about something which doesn't exist true or false?

Let S = {x | x is not an element of x } The set S doesn't exist. Then, would a proposition such as "The cardinality of S is 1," be true or false? Equivalently, I could have made a proposition, "the ...
6
votes
1answer
270 views

distribution of categorical product (conjunction) over coproduct (disjunction)

In the classical and intuitionistic propositional calculi, it is straightforward, using natural deduction, to derive $((A \land C) \lor (B \land C))$ from $(A \lor B) \land C$: Assume $(A \lor B) ...
6
votes
3answers
318 views

How complicated is the set of tautologies?

Consider the set $\mathcal T$ of all tautologies in the propositional calculus in which the only operators allowed are $\to$ and $\neg$, and involving only the two variables $x$ and $y$. How ...
3
votes
3answers
281 views

Proving that the theorems of one logistic system are also theorems of another logistic system

Question: I am developing the proof for the following exercise from An Introduction to Mathematical Logic and Type Theory: To Truth Through Proof by Peter B. Andrews: X1102. Let $\mathscr{M}$ be ...
2
votes
2answers
208 views

Propositional Calculus and “Lazy evaluation”?

I want to formalize a system, and currently I don't know, if I can use propositional calculus in my case. At first, I though that I need a simple conjunction. $A \wedge B$ However, there is a ...
1
vote
4answers
78 views

Need Hints Prove “$((\neg \alpha \to \alpha) \to \alpha) $” Using Axiom 1,2,3 and MP and deduction theorem

$((\neg \alpha \to \alpha) \to \alpha) $ Hi, I am trying to prove this. Can someone gives me some hints to start the question... My friend told me I might need to use deduction theorem here, but I ...
5
votes
2answers
2k views

What's the difference between a negation and a contrapositive?

What's the difference between a negation and a contrapositive? I keep mixing them up, but it seems that a contrapositive is a negation where the terms' order is changed and where there is an imply ...
3
votes
3answers
88 views

If $(A \vee B) \wedge (¬B \vee C)$ is true, then $(A \vee C)$ must be true … can I argue that?

If $(A \vee B) \wedge (¬B \vee C)$ is true, then $(A \vee C)$ must be true ... can I argue that? I don't see how I can argue that $(A \vee C)$ must be true because can't we have $(T \vee T) ...
2
votes
2answers
183 views

Proving and Modeling Logical Consistence

Suppose I have a finite list of logical statements (would these be called axioms?) and for the sake of discussion say that there are 6 such statements. All statements are in the form of propositional ...
2
votes
1answer
1k views

Relation between XOR and Symmetric difference

I noticed that XOR and symmetric difference use the same symbol, $\oplus$. They also seem to have a similar structure: XOR: $(\neg P\wedge Q)\vee(P\wedge \neg Q)$ Symmetric Difference: $(A\cap ...
1
vote
2answers
505 views

Definition of “contradiction” and use of the term for “⊥”

If one looks in Internet for definition of “contradiction” (including respective words in other languages), one finds a mess. See for example this index of Wikipedia articles in various languages. The ...
1
vote
1answer
76 views

Proving that a propositional theory of any cardinality has an independent set of axioms

This is exercise 1.2.19 from Chang & Keisler's Model Theory, which has been giving me a headache for some time now. Let $\mathscr{S}$ be a given propositional language of any cardinality (i.e. ...
0
votes
0answers
79 views

Let Γ = {p∧q,(¬p)∨q,p∨r}. Is it true that Γ ⊢ r?

I"m not sure how to solve this type of question. Here is the problem in more detail, and a similar problem: I know that given this set of formulas I'm supposed to show if its possible to deduce r ...