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)

6
votes
7answers
3k views

Associativity of logical connectives

According to the precedence of logical connectives, operator $\rightarrow$ gets higher precedence than $\leftrightarrow$ operator. But what about associativity of $\rightarrow$ operator? The implies ...
4
votes
1answer
86 views

How to prove Post's Theorem by induction?

The proof of post's theorem is given in my textbook in two pages of explanation using a non-induction method. I was told that ,using induction on length of the proof, one can get a simpler and more ...
-2
votes
0answers
31 views

primitive recursive predicate challenge [duplicate]

I see this question as a nice challenge on logic. Primitive Recursive Predicate Problem if P(x) and Q(x) be a primitive recursive predicate. which of the following is not a primitive recursive? ...
1
vote
1answer
32 views

How to prove this logical equivalence using different laws?

Prove that $﹁p → (q→r)$ and $q → (p∨r)$ are logically equivalent using different laws. this is my answer: $﹁p → (q→r) = q → (p∨r)$ $(q→r) = ﹁q∨r$ implication equivalence $﹁p → (q→r) = p∨(﹁q∨r)$ ...
1
vote
1answer
53 views

How to prove theorems using axioms and lemmas [closed]

How do I prove the following? Theorem L 10. $(\sim B \implies \sim A) \implies (A \implies B)$ Theorem L 11. $\sim \sim B \implies B$ Theorem L 12. $B \implies \sim \sim B$ We are actually ...
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)$. ...
-1
votes
1answer
67 views

Logic Challenging Question

I see this statement on the book: Assuming a set $\Sigma = \{ φ_1, φ_2, \ldots \}$, for each valuation v, we have n such that $v(\varphi_n)=1$. in this case we have n, such that: $\vDash \varphi_1 ...
0
votes
2answers
70 views

Is it always a tautology?

If any two compound propositions $P$ and $Q$ are equivalent, then is the proposition formed from their biconditional $P \leftrightarrow Q$ always a tautology?
3
votes
2answers
102 views

Model-theory and Proof-theory in Propositional Logic

I'm trying to link results of model theory and proof-theory in propositional language. Here i will use $\models$ to denote logical consequence, in the model-theory sense. Being $x,y$ two formulas of ...
1
vote
1answer
92 views

Prove that the disjunctions of all conjucts is a disjunctive normal form

Question: I am attempting the following exercise from An Introduction to Mathematical Logic and Type Theory: To Truth Through Proof by Peter B. Andrews: X1408. Prove that if $\mathbf{A}$ is a wff ...
1
vote
1answer
34 views

Correctly understanding truth table problem?

I'm typing up a solution set for an "intro to proof" course. One of the problems asks the student to "construct a truth table for $(P \implies Q) \implies (\neg P)$." I interpreted this as requesting ...
3
votes
0answers
37 views

Proving a graph has a property if all finite subgraphs have that property

Given a graph $G=(V,E)$ and an integer $k\in\mathbb N$, we will say that $G$ is $k$-good if: for every division $V=\bigcup_{i\in I} U_i$ such that $i\not=j \Rightarrow U_i\cap U_j =\emptyset$ and ...
3
votes
3answers
108 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 ...
0
votes
3answers
164 views

Logic Confusing Problem

I Read one logic book, can my two conclusion are true? 1- Suppose for each valuation v, we have such n that can we say we have such n that 2- Suppose for each ...
4
votes
3answers
182 views

Simplifying a categorical proof of constructive dilemma

In axiomatic propositional calculus the following axiom schema captures constructive dilemma: $\newcommand{\lif}{\supset} \renewcommand{\land}{\&}$ \begin{equation} (a \lif c) \lif ((b \lif c) ...
1
vote
2answers
228 views

Proving in a Hilbert system that $\neg A\Rightarrow A$ is a theorem, if assuming $\neg A$ makes it contradictory

Consider a Hilbert system $\mathcal{T}$ with modus ponens as the unique deduction rule, and subject to the following four axioms: $(R\lor R)\Rightarrow R$. $R\Rightarrow (R\lor S)$. $(R\lor ...
1
vote
3answers
69 views

prove validity of following sequent

How to prove validity of following sequent using rules of conjunction, disjunction, implication, negation etc. Premises: $ c \wedge n \Rightarrow t$ , $h \wedge \sim s$, $h \wedge \sim(s\vee c) ...
1
vote
2answers
69 views

How to deal with equivalences in proofs?

There is a part I need clarification on regarding the use of equivalence and its symmetry. From what I understand in regards to symmetry is that: $ (p \equiv q) \equiv (q \equiv p) $. Given p and q ...
0
votes
0answers
25 views

How to express following declarative sentences in propositional logic?

How to express following declarative sentences in propositional logic? 1) No shoes, no shirt, no service 2) My sister wants a black and white cat
0
votes
1answer
33 views

How to prove validity of following sequent [closed]

How to prove validity of following: Premises: $p\rightarrow q$, $s\rightarrow t$, Conclusion: $(p \lor s) \rightarrow (q\land t)$
2
votes
1answer
98 views

About $\Sigma=\{p_2\to p_1, p_3\to p_2,\, \dots\,\}$ . . .

Suppose $$\Sigma=\{p_2\to p_1, p_3\to p_2,\, \dots\,\}.$$ Which of the following is true? Explain your answer. For any $n$, $$\Sigma\cup\{p_n, \neg p_{n+1}\}$$ is complete and ...
7
votes
4answers
161 views

How or why does intutionistic logic proof negations from within the theory, constructively?

I'm having a little of a cognitive dissonance why, in intuitionistic logic, it's possible to show stentences like $(\neg A \land \neg B) \implies \neg(A\lor B).$ In plain text: If 'A isn't true' as ...
-1
votes
4answers
105 views

Which of $\varphi$ or $\lnot \varphi$ can be expressed by using only the $\rightarrow$ connective? [closed]

if we have: $$\varphi = \lnot(p\land q\to r) $$ (original screenshot) a) we can write $\varphi$ in equivalence just by using $\to$ connective. b) we can write $\lnot\varphi$ in equivalence ...
2
votes
5answers
95 views

Propositional logic: Why is there values in “$\lor$” and “$\neg$”?

I'm having some difficulties in understanding why there are values under the symbol $\lor$ and $\neg$ in the truth table. Could someone explain me why and/or how you give a value to a symbol or is ...
-1
votes
1answer
56 views

Quick Truth Table in Logic Problem

Suppose We Have: How can quickly detect how many "1" are in the truth table of above formula? (without drawing Truth Table). i think by using some inference. any idea? we know there are 11 "1"s ...
1
vote
1answer
56 views

Prove A or (A and B) is equivalent to A [duplicate]

Prove $A \lor (A \land B) \Leftrightarrow A$ without using truth table. The proof may involve expanding $B$ into $B \land B$ or possibly $B \lor B$. I am stuck after playing with distributive law ...
1
vote
1answer
31 views

Discrete math and rules of inference

I recently did this rules of inference/logic question and the method I used was different from the textbook so I was wondering if my work was correct?
-1
votes
3answers
43 views

Help with function proof [closed]

I am asked to prove or disprove that if $f:A\rightarrow B$ is a function, then: If $Y\subseteq B$, then $f^{-1}(B\setminus Y) = f^{-1}(B)\setminus f^{-1}(Y)$. I have no idea how to go about doing ...
1
vote
1answer
331 views

proof of validity of tautology in first order logic

Every first-order logic formula which has a tautological shape in propositional logic is a valid formula. Will it be possible to give a formal proof for the above ? Thanks and Regards.
1
vote
3answers
86 views

Can a statement in FOL be equivalent to two separate independent statements?

This may seem like a dumb question, and it certainly seems dumb to me asking it, but I'm running into a contradiction. I'm looking at the problem of finding a statement $\phi$ such that $\psi$ and ...
0
votes
1answer
42 views

Logic Pure Subset Problem

for example if we define : $$ \$(p,q,r) = (p\to q)\land(\neg p\to r)$$ how we can inference that set $\{\$,\top,\bot\}$ is Full Functional and not any pure subset of this be full functional.
1
vote
1answer
32 views

From statement to logic

I have a problem with the modelling of the following statement in propositional logic (warning, I translated it from italian): Martha is not a singer, and she doesn't play violin or flute, but not ...
1
vote
1answer
34 views

Rules of inference: The Rules of Disjunctive Syllogism and Double Negation

I have a question about the use of Double Negation in relation to this problem I found in my textbook examples. Problem: $\;¬(r \land t) \lor u$ $\;r \land t$ Therefore, $u$. In my textbook it ...
2
votes
1answer
21 views

Proposition Question

I am trying to translate this into propositional symbols but (for me) it's so complicated. Can someone help me figure this out. "If it rains then I will carry a sharp object and I will start laughing ...
11
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
2answers
273 views

**Competition** Shortest Proof of Lukasiewicz's 13 Letter Axiom for Implicational Calculus from Tarski-Bernays

Spurred on by Willemien's competition, I thought I'd post my own. In 1948 a paper by Jan Lukasiewicz got published that established a 13 letter formula as (one of?) the shortest single axioms, under ...
2
votes
4answers
57 views

Hilbert System with propositional logic $p \rightarrow q,\neg q \vdash \neg p$

This is my set of axiom $A \rightarrow (B\rightarrow A)$ $(A\rightarrow(B\rightarrow C))\rightarrow ((A\rightarrow B) \rightarrow (A \rightarrow C))$ $(\neg A \rightarrow B)\rightarrow ((\neg A ...
0
votes
2answers
50 views

Can There Get Found Single Axioms for Some Subsystems of Propositional Calculus?

I use Polish notation. All systems have detachment and uniform substitution as the only primitive rules of the system. A user named John told me in an answer "On the question of a single axiom, the ...
0
votes
2answers
63 views

How to express $\lnot (a < b < 0)$ or the contrapositive of this statement?

I can't seem to get the negation, $\lnot (a < b < 0)$, right. I thought I could break it into 3 parts: a < b, a < 0, b < 0, but that leaves me with a > b or a > 0 or b > 0 (greater or ...
2
votes
1answer
55 views

A simpler derivation of ($\phi \lor (\neg \phi)$)

In Chiswell&Hodges [Ian Chiswell & Wilfrid Hodges, Mathematical Logic (2007)] they use this derivation to prove ($\phi \lor (\neg \phi)$): A page earlier they used a simpler derivation that ...
3
votes
2answers
92 views

Why is removing the negation worse than adding it?

Natural Deduction Rule (¬I): Natural Deduction Rule (RAA): My book [Ian Chiswell & Wilfrid Hodges, Mathematical Logic (2007)]presents these two rules and then adds: The use of (RAA) can ...
2
votes
5answers
84 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 ...
1
vote
1answer
39 views

Is there a proof of this statement about deductions?

Is there a proof of the following statement: you cannot prove with natural deduction theorems that are unprovable in a Hilbert-style proof system? The logic in discussion is either propositional logic ...
4
votes
4answers
76 views

Find propositional formulas $\phi$ and $\psi$ such that $(\phi \rightarrow (\psi \rightarrow (¬\psi)))$ is a theorem of L.

Find propositional formulas $\phi$ and $\psi$ such that $(\phi \rightarrow (\psi \rightarrow (¬\psi)))$ is a theorem of L. So every axiom is a theorem of L so I thought there would be some way to ...
3
votes
3answers
103 views

Fitch-Style Proof

Hi I'm having trouble solving a Fitch Style Proof and I was hoping someone would be able to help me. Premises: $A \land (B \lor C)$ $B \to D$ $C \to E$ Goal: $\neg E \to D$ Thank You
2
votes
1answer
56 views

Fitch-Style First Order Logic

I have been stuck on this proof for a while. Here's where I'm at: Goal $(\neg B \to \neg A) \leftrightarrow (A \to B)$ l 1. $A \to B$ ll 2. $\neg B$ lll 3. $A$ lll 4. $B$ Elim 1,3 ...
4
votes
3answers
141 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
3answers
244 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 ...
1
vote
1answer
37 views

The logical consequence of an empty set of premises.

I am studying propositional logic by self-study, using a dutch book. I hope I am translating the terms to the correct English term. If my words are confusing, please please just let me know instead of ...
0
votes
1answer
22 views

How does the propositional logic of the following IFF proof (DAGs and topological ordering) work?

I was reading the following proof and am having trouble following the propositional logic underpinning the proof: http://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/Graph/DAG.html To ...