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)

-1
votes
0answers
14 views

logical consequence [on hold]

I have been asked to prove the following formula related to Logical Consequence. I have searched through the math stackexchange site, but I havent really found anything that fits what I am looking ...
1
vote
0answers
34 views

Hilbert style proof for $ \left( \left( A\rightarrow \left( A\wedge \neg A\right) \right) \rightarrow \left( A\rightarrow A \right) \right) $

How can I proof that the following formula is a tautology by using Hilbert calculus? $ \left( \left( A\rightarrow \left( A\wedge \neg A\right) \right) \rightarrow \left( A\rightarrow A \right) ...
1
vote
2answers
56 views

Is $((p\rightarrow q) \land \neg p) \rightarrow \neg q$ a tautology?

Is this proposition a tautology? $((p\rightarrow q) \land \neg p) \rightarrow \neg q$ Knowing that $\alpha \rightarrow \beta$ is equivalent to $\neg \alpha \lor \beta$, I have come up with ...
2
votes
1answer
34 views

Show that for propositional logic $\vdash_i \neg \varphi \Leftrightarrow \vdash_c \neg \varphi$.

As the title says, where $\vdash_i$ is derivations in Intuitionistic logic and $\vdash_c$ is derivations in Classical logic. I am allowed to use a corollary that states that $\vdash_i \varphi ...
0
votes
1answer
21 views

Proof for association law?

I am new in logic and I getting a little bit confused with maths. Can I do something like this following the Associative Law? $$(p ∨ ¬r) ∨ (r ∨ ¬p) ≡ (p ∨ ¬p) ∨ (r ∨ ¬r)$$ Thank you in advance for ...
0
votes
1answer
17 views

Hilbert style proof of double negation introduction and reductio ab adsurdum

I'm trying to prove: $\phi\to\neg\neg\phi$ $(\neg\phi\to\neg\psi)\to((\neg\phi\to\psi)\to\phi)$ Using these axioms with modus ponens and the deduction theorem: A1: $\phi\to(\psi\to\phi)$ A2: ...
3
votes
0answers
38 views

How many ternary functionally complete connectives are there?

Today I was reading up once more on some of the nice results regarding functional completeness, notably Post's celebrated classification theorem with the 5 classes that need to be avoided. (See this ...
0
votes
0answers
33 views

In classical logic ~~p -> p? Intuitionistic?

Is the following rule applicable in classical propositional logic? $\sim (\sim p)\rightarrow p$ In my textbook, it shows that $p \rightarrow\sim(\sim p)$ holds for intuitionistic logic but I was ...
0
votes
2answers
25 views

Prove/disprove a propositional statement

I have a homework question that I've been struggling with. I need to prove or disprove that: $(p ∧ (q ∨ r)) \to (r ∨ (q ∨ p)) = p ∨ q$ I've already constructed the first step of the proof which is ...
2
votes
1answer
36 views

how to give a truth value for the following formula

I am trying give a structure that makes that makes the formula T and a structure that makes the formula F for the following formula ...
0
votes
1answer
22 views

proof verification for natural deduction

Could someone please let me know if I got the following natural deduction correct for the following formula ...
0
votes
0answers
32 views

Create the following wffs(axiom rules for domain) for the domain of lists over alphabet A

Recall that in the domain of Lists over Alphabets, the function cons(a,x) where a is an element in an alphabet and x is a list, produces a new list with a at the beginning of L. The predicate ...
0
votes
1answer
108 views

Progressing in Propositional Logic

I am self-studying precalculus-level mathematics in perhaps a more formal way than usual, which means that I am reading about logic, sets, proofs, etc. The text I am looking at contains as an example ...
-1
votes
1answer
22 views

Prove the following using only axioms of propositional logic and the deduction theorem? [see description] [closed]

$\vdash((\alpha\implies\beta)\implies(¬\beta\implies¬\alpha))$ Give a proof for the above theorem using only the three axioms of propositional logic (below), modus ponens, and the deduction theorem. ...
0
votes
1answer
769 views

Disjunctive normal form (BOTH dnf and cnf) example help

T or ( not x and y ) or ( x and y ) In class we went over examples of how many things can be both DNF and CNF... eg. (not z) or y can be thought of as both (not z) or y .... dnf ((not z) or ...
0
votes
2answers
36 views

Formal logic proof verification

I am trying to prove the following sequent formally. $$P, (P \land Q)\Rightarrow \sim R \vdash R\Rightarrow \sim Q$$ I have come up with the following formal proof, but I am not completely sure if ...
0
votes
2answers
50 views

$P ⇒ (Q ∨ S)$ , how can I prove $Q$?

I'm asking this in the context of a logical programming language similar to Prolog. Say I have the rule $P ⇒ (Q ∨ S)$ . How would I go about proving the truth value of $Q$, assuming I know the ...
0
votes
1answer
7 views

Conjunctive Normal Form (CNF) of a propositional formula

These are my notes for Discrete Math. I'm having trouble understanding how to convert the given formulae at the end into CNF. The example seems to have skipped the steps and jumped straight to the ...
1
vote
1answer
24 views

Associativity? Can this be applied here?

As the Associativity law says that (A ∧ B) ∧ C ≡ (A ∧ C) ∧ B, can I do something like this? (A ∧ ¬B) ∨ (B ∧ ¬A) ≡ (A ∧ ¬A) ∨ (B ∧ ¬B) I am new with logic and I still don't get this basic ...
1
vote
2answers
55 views

Can an open statement be a tautology?

A tautology is a statement which is true by dint only of the logical connectives contained therein. My question is about a statement which contains an unquantified variable. For example: P: ($x$ ...
0
votes
1answer
26 views

Set theory statements vs. propositional statements

I was wondering if statements that hold in general in set theory, such as De Morgan's Laws, always hold in propositional logic as well. If not, what are some examples of such statements that in the ...
0
votes
2answers
404 views

Prove using a proof sequence and justify each step

Prove using a proof sequence that the argument is valid [ A --> (B ∨ C) ] ∧ B' ∧ C' --> A' I'm having some trouble figuring the proof out here. Here is what I have so far. Is this on the right ...
1
vote
4answers
40 views

Showing that $(A \land B)' \land (C' \land A)' \land (C \land B')' \to A'$ without a truth table

Problem: Prove that $(A \land B)' \land (C' \land A)' \land (C \land B')' \to A'$. What I have done so far: $(A \land B)'$ premise $(C' \land A)'$ premise $(C \land B')'$ premise $A' \lor B'$ ...
2
votes
3answers
101 views

Logic Behind Epsilon-Delta Proofs (Single-Variable Calculus)

Most of what I am asking is based off this (fairly popular) article I've read here : https://bobobobo.wordpress.com/2008/01/20/how-to-do-epsilon-delta-proofs-1st-year-calculus/, but most lecturers, ...
1
vote
1answer
36 views

A faster way of proving that a 'theorem' (logic) is true.

Suppose I want to prove that the following is a theorem. $$\left [ \left ( P \vee Q \right ) \Rightarrow R \right ] \Rightarrow \left [ \left ( P \Rightarrow R \right ) \vee \left ( Q \Rightarrow R ...
1
vote
2answers
29 views

Proofs Using Tautologies

Let's say I want to formally prove a statement of the form $$p \implies q$$ So I do a bit of work,some re-arranging and eventually I arrive at a statement of the form $$p \implies p$$ which is a ...
0
votes
2answers
557 views

Solving Logical equivalence & propositional logic problems without truth tables

I have no particular "Logic question" in hand at the time being, but need help to understand a way that can be used to prove "Logical equivalence without using truth tables". moreover can we solve ...
3
votes
2answers
562 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. Is it possible to give a formal proof for the above?
1
vote
2answers
21 views

Does the fact that a modal operator distributive over disjunction imply that a modal operator is distributive over conjunction?

If L is an arbitrary operator on two propositions p and q: Does L(p $\vee$ q) $\Rightarrow$ Lp $\vee$ Lq imply L(p $\land$ q) $\rightarrow$ Lp $\land$ Lq?
0
votes
0answers
28 views

How to show that $\lnot q \equiv (p \lor q) \rightarrow p$?

How I can show that $\lnot q \equiv (p \lor q) \rightarrow p$ are equivalent using Law of Algebra Propositional ? I applied in this order: $(p \lor q) \implies p$ implication DeMorgan ...
1
vote
1answer
19 views

Resolution proof involving more than a literal

I want to show that the following clauses are unsatisfiable together using resolution (i.e. obtain a refutation): 1: $\lnot P_1 \lor \lnot P_2$ 2: $P_2 \lor \lnot P_3$ $P_1 \land P_3$ I perform ...
2
votes
1answer
15 views

conditional proposition vs biconditional proposition

So I have been working on college and am currently in a math class. The following question came up and I chose "->" as the answer. This was marked wrong and I challenged the answer but was told this ...
0
votes
2answers
36 views

finding a formula for a given truth table

How would one proceed in finding a formula from a given truth table without resort to the use of disjunctive normal form and karnaugh maps? For example, given ...
0
votes
1answer
24 views

Equivalence classes in the logical equivalence on some finite set of propositional formulas

I'm having trouble understanding the following problem: Let $S_n$ be the set of all formulas that can be built up with the atoms $\{A_1,...,A_n\}$. How many equivalence classes does the ...
2
votes
3answers
607 views

Determine whether the argument is valid or invalid

$\;(\lnot p \lor q)\land (\lnot p \rightarrow q)$ $\;\;\;\;p$ $\overline{\therefore\;\lnot q\qquad}$ Valid or invalid: How would I approach this problem? Thanks for the help.
2
votes
1answer
34 views

Q: Is the set of all binary connectives having an even number of Truth in their truth table is functionally incomplete?

Is the set $TC$ of all binary connectives having an even number of Truth values assigned to the entries of their truth table (i.e. 0, 2 or 4) is functionally incomplete? It's easy to see that the ...
1
vote
1answer
65 views

proof that $\{\rightarrow, \land \}$ is not a complete set of logical connectives

I need some help to prove that the set $\{\rightarrow, \land \}$ of logical connectives is not a complete set. can someone help me to understand what should I do? thanks!
1
vote
0answers
82 views

Disproving $\neg Q$ proves Q in all cases?

Does disproving the negation of a claim prove the claim in all scenarios and sufficient enough to say Q is true? Even if Q is an implication, or an equality, or etc? What about vacuous truths? Can ...
0
votes
1answer
20 views

Counterexamples of existentially quantified statements

I just realized I have a serious problem in properly seeing the logical structure that involves counterexamples. Here there is an example: Proposition F: Assume $P$. Then, there is a function $f ...
0
votes
2answers
34 views

propositional calculus problem, how to prove this right or wrong?

$A$$\rightarrow$$(B$ $\vee$ $C$ ) , $B$ $\rightarrow$ $C$ $\vDash$ $A$ $\rightarrow$ $D$ I think it's wrong but I have no idea how to prove.
6
votes
3answers
660 views

Give a proof that “p & ~p” implies “q”?

Context: This is not a textbook or homework problem. I was hoping you younger folks could help my tired old brain. "Everybody knows" a contradiction implies anything. What I'm looking for is a ...
1
vote
5answers
74 views

Propositional logic - Natural deduction

I'm stuck with a big proof in my homework. I have to use natural deduction to prove something, and I think if I can prove this somehow then I can finish the full proof. Can anyone help? P v Q, ¬P : Q ...
0
votes
1answer
16 views

$\Sigma$ is maximally satisfiable $\iff$ there exists $M$ such that $\Sigma=\{\alpha \mid M\vDash \alpha\}$

A set of formulas $\Sigma$ is maximally satisfiable $\iff$ there exists $M$ such that $\Sigma=\{\alpha \mid M\vDash \alpha\}$. I have easily proved that if $\Sigma$ is maximally satisfiable than ...
0
votes
2answers
32 views

Decide if $((((P\wedge Q)\wedge R)\wedge S)\wedge T)\Rightarrow(\neg P\vee T)$ is a tautology

How can I show that $((((P\wedge Q)\wedge R)\wedge S)\wedge T)\Rightarrow(\neg P\vee T)$ is a tautology? I tried to apply the implication rule $(p\Rightarrow q)\equiv (\neg p\vee q)$ but it doesn't ...
0
votes
1answer
35 views

Is this a valid propositional natural deduction proof?

I'm new to logic and I tried to solve an exercise. Since there isn't a given answer, I'd appreciate an indication of whether this is correct ...
1
vote
1answer
21 views

logic: derive a formula using laws

Let's say I have the following formula: $$(A\wedge\neg C)\vee(B\wedge C)\vee(A\wedge B).\tag{1}$$ It is easy to show following: $$(A\wedge\neg C)\vee(B\wedge C)\vee(A\wedge B)\Leftrightarrow ...
0
votes
1answer
1k views

Expressing the converse, contra-positive, and inverse of conditional statements

This problem is from Discrete Mathematics and its Applications Here is my book's definition on converse, contrapositive, and inverse And the common ways to express an implication For this ...
1
vote
1answer
41 views

Truth table and induction

It is true that every truth table can be represented by some wff built using only the connectives $\neg, \implies$ and $\iff$ - let's call it "negation-arrow-wff" for convenience. I want to be able to ...
0
votes
0answers
13 views

Show that if X implies Y is valid, then X is unsatisfiable or Y is valid

How can I show that if X and Y are two formulas with no propositional variables in common, and (X ⇒ Y) is valid, then either X is unsatisfiable or Y is valid (or both). I know that (X ⇒ Y) is false ...