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)

47
votes
17answers
4k 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: ...
16
votes
8answers
11k views

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

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\\ ...
17
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 ...
4
votes
4answers
6k 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
5answers
468 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$?
7
votes
8answers
614 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 ...
5
votes
3answers
521 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 ...
6
votes
5answers
836 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 ...
1
vote
2answers
70 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 ...
13
votes
2answers
2k 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 ...
8
votes
2answers
19k 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 ...
8
votes
6answers
2k 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)$. ...
5
votes
3answers
583 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$ ...
5
votes
3answers
269 views

Show by using logical connectives laws that $(P\to Q) \land (Q \to R) $ is equivalent to $(P \to R) \land [(P \iff Q) \lor (R \iff Q)]$

I am having trouble with a problem in the book I'm self-studying from. It says the following: Show that $(P\to Q) \land (Q \to R) $ is equivalent to $(P \to R)$ $\land [(P \iff Q) \lor (R \iff ...
3
votes
1answer
261 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
141 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
325 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
70 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
100 views

prove $( \lnot \lnot p \Rightarrow p) \Rightarrow (((p \Rightarrow q ) \Rightarrow p ) \Rightarrow p )$ with intuitionistic natural deduction

I'm trying to prove this statement with intuitionistic natural deduction using inference rules like this example : this is the statement I'm trying to solve : $$( \lnot \lnot p \Rightarrow p) ...
0
votes
1answer
98 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
363 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
5answers
275 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
5answers
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 ...
3
votes
3answers
2k views

How does “If $P$ then $Q$” have the same meaning as “$Q$ only if $P$ ”?

Every lecture that I watched on mathematical logic and my textbook say that $P \Rightarrow Q$ has the same meaning as $\text{"If $P$ then $Q$"}$ which has the same meaning as $\text{$Q$ only if ...
3
votes
3answers
314 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
1answer
87 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 ...
1
vote
4answers
104 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 ...
1
vote
1answer
64 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 ...
0
votes
2answers
176 views

Completness and Set of Result of One Set ?!?

Dear Everyone on this Wonderful Sites: I'm so glad to participate on this site and ask the first question that mentioned on the Contest some days ago. I ran into a question that wrote this set: ...
8
votes
3answers
1k 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?
7
votes
4answers
188 views

Showing $(P\to Q)\land (Q\to R)\equiv (P\to R)\land[(P\leftrightarrow Q)\lor (R\leftrightarrow Q)]$ {without truth table}

Problem: Show $(P\to Q)\land (Q\to R)\equiv (P\to R)\land[(P\leftrightarrow Q)\lor (R\leftrightarrow Q)]$ Source: As was noted in the original post, this problem is from Daniel J. Velleman's book ...
3
votes
2answers
111 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
745 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, ...
3
votes
3answers
393 views

Distinguishing between valid and fallacious arguments (propositional calculus)

I am having some difficulties understanding logical arguments. I was taught that the notion of a valid argument is formalized as follows: "An argument $P_1, P_2,\cdots , P_n ⊢ Q $ is said to be ...
2
votes
3answers
264 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
94 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
179 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
6answers
134 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 ...
3
votes
2answers
200 views
3
votes
5answers
1k 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
3answers
170 views

Problem solving Logical Equivalence Question

I am working with Logical Equivalence problems as practice and im getting stuck on this question. Can somebody help? Im trying to show that The LHS is equivalent to the RHS (¬P ∧ ¬R) ∨ (P ∧ ¬Q ∧ ¬R) ...
2
votes
1answer
127 views

Show that the conditional statement is a tautology without using a truth table

I have been attempting to use identities to get to the answer but I am unable to get anywhere. Here is the equation I am trying to prove tautological without using truth tables: $[(p\rightarrow q) ...
2
votes
2answers
226 views

Deducing $(\lnot B) \to A$ from $\lnot A \to B$ using Hilbert deductive system

As the title says, I've been trying to prove this: $(\lnot A \to B) \vdash (\lnot B) \to A)$ but unfortunately keep winding up with crazy long steps and then I have no idea where to go. The only ...
2
votes
2answers
133 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
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
1answer
53 views

Show that $\neg$ and $\wedge$ form a functionally complete collection of logical operators.

Earlier this day I ask about the assignmet: Show that $\neg$ and $\wedge$ form a functionally complete collection of logical operators. I was given the hint that I could use De Morgan law to show ...
1
vote
2answers
98 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
1answer
60 views

Let $\tau$ and $\rho$ be tableaus such that $\tau \leadsto \rho$. Prove that $\tau$ is satisfiable if and only if $\rho$ is satisfiable.

I have this definition: Let $\nu$ be any propositional interpretation. Let $b$ be any branch of a tableau. Say that $\nu$ is faithful to b if and only if for every formula, $A$, on the branch, ...
0
votes
3answers
156 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} $$$$ ...