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)

-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)$ ...
4
votes
1answer
87 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 ...
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 ...
-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?
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 ...
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) ...
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
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
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)$
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 ...
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 ...
-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
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 ...
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
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 ...
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
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 ...
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 ...
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
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 ...
0
votes
2answers
64 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
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 ...
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
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 ...
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 ...
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
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 ...
0
votes
0answers
59 views

alternative Compactness theorem proof

I'm attempting a problem which requires me to prove the compactness theorem for propositional logic ![enter image description here][1]in a slightly different way to normal. I'm struggling to ...
4
votes
1answer
35 views

Discrete 101: Validity of proof: Finding that p→q ∨ ¬r, q→p∧r, therefore p→r is invalid.

I'm sorry to bother with what apparently is a very easy Basic Logic question, but in my class'es notes there's an example that the professor probably explained in class: ...
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 ...
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
4
votes
3answers
246 views

P entails Q implies P

I have been looking at the following: P entails Q implies P And developed the proof as follows: ...
3
votes
4answers
215 views

How to prove this type of equivalence?

Show that from: $P \ \rlap\Leftarrow\Rightarrow Q$. It follows that: $(P \Rightarrow R)\, \rlap\Leftarrow\Rightarrow (Q \Rightarrow R)$ I don't understand where the $R$ suddenly came from? I try to ...
0
votes
1answer
89 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.
2
votes
1answer
29 views

Write $(p\land q)\leftrightarrow (\neg p\lor \neg q)$ in CNF

I need to convert the below for a homework question and I am not entirely sure if it's correct. The last part is that I am not sure how to use the distributive laws in this scenario. Any guidance ...
0
votes
2answers
48 views

Using DeMorgan’s rule, state the negation of the statement

Using DeMorgan’s rule, state the negation of the statement: “The car is out of gas or the fuel line is plugged.” Let C stand for “The car is out of gas” and let F stand for “the fuel line is ...
2
votes
1answer
65 views

Understanding the connective '$\vee$'

I have just started studying mathematical reasoning and have come through one simple foolish problem. I have learn that if '$\vee$' is used as connective and if any one component statement is true ...
1
vote
1answer
54 views

Using the compactness theorem

I am working through problems which ask you to apply the compactness theorem (from propositional logic) to problems. How would you go about solving this one? Let $\mathbf{L}$ be an arbitrary ...
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 ...
0
votes
2answers
98 views

Solving a contradiction in premises

I've got a set of premises: $m \rightarrow j, a \rightarrow j, \neg m \rightarrow a, a \rightarrow \neg j$ Clearly, $a \rightarrow \neg j$ Contradicts $a \rightarrow j$ I'm asked to proof that out ...
0
votes
1answer
36 views

Help with axiom in propositional logic

I have an example in a propositional logic course I'm taking and I can't figure out how a certain axiom is/why it is applied in a certain step. This link: http://www.logicinaction.org/docs/ch2.pdf ...
0
votes
1answer
64 views

Conditional Introduction Rule

In the derivation (the image below) the author shows that given the premise $\neg S \land \neg J$, the conclusion is $S \implies J$. All these deductive maneuver for concluding implications I find ...
1
vote
3answers
39 views

Propositional logic De-morgans theorem question

the theorem states that $(A\wedge B) = \neg (\neg A\vee \neg B)$, where $A$ and $B$ are propositional formulas. Can't I turn $\neg (\neg A\vee \neg B)$ to $(\neg \neg A\vee \neg \neg B)$ then cancel ...
1
vote
2answers
83 views

Negation rules in natural deductive systems

This question concerns the block of text at the bottom, which is from Teller's Logic Primer, Chapter 5 (page 72). (I must mention that there is a rule called Negation Introduction. It says that when ...