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)

3
votes
0answers
42 views

Strict order on propositions and interpolation

We can define a strict order on the set of propositions in countably many propositional letters in the following way: $$\varphi\sqsubset\psi \iff (\models \varphi\rightarrow\psi)\, \land (\not\models ...
0
votes
4answers
94 views

Why is “$A$ unless $B$” equivalent to $A \lor B$?

$A$ unless $B$ surely means, 'given that $B$ does not happen, $A$ will happen'. So if $B$ happens, $A$ does not happen. Yet I've read, by those officially accredited, that $A$ unless $B$ = $A$ or $B$...
-1
votes
2answers
74 views

Should we change the truth table for the material conditional?

Having studied logic, I still cannot understand the conditional. At first, it was because (as with most things I learn) it was a problem with my understanding. I now believe it is because there is an ...
3
votes
4answers
48 views

Using Logic Laws to prove $p \leftrightarrow q \equiv (p\lor q)\to(p \land q)$

I am trying to prove that $p \leftrightarrow q \equiv (p\lor q)\to(p \land q)$ and am really lost in the steps to solve this. So far I have: $p \leftrightarrow q \equiv (p\to q)\land(q\to p)...
0
votes
1answer
42 views

Meaning of “$r \to s$ is a tautology” in the definition of “implication” and “equivalence”

What does it mean to say the following: $$ r \to s\ is\ a\ tautology$$ I make the following truth table: $$\begin{array}{ l c c r } r & s & \lnot r & r \to s \\ \hline T & T &...
0
votes
1answer
37 views

Proving general proposition using HPC

If I have a general Proposition $c$ in HPC + another axiom that $(a \rightarrow b)$. HPC axioms - $$1 .a \rightarrow (b \rightarrow a)$$. $$2. (a \rightarrow (b \rightarrow c))\rightarrow ((a\...
1
vote
2answers
43 views

Modus Ponens: why it should not work

The scenario I'm analyzing is the following: I have the set of clauses $${ ( \neg A \Rightarrow B ),\, ( B \Rightarrow A ),\, ( A \Rightarrow ( C \wedge D ) ) }$$ and I have to prove the ...
0
votes
2answers
17 views

Simplifying propositional logic formulae

Prove $\neg ((P\land Q)\lor \neg (P\land T)\lor (Q\land T)) \equiv P \land \lnot Q \land T$ Using only De Morgans Laws and the Distribution Laws. I managed to get the left hand side to reduce to the ...
-1
votes
1answer
12 views

How to use parentheses with one logical conective? [closed]

is (((a and b) and c) and d) equal to a and b and c without parentheses? Why?
1
vote
2answers
45 views

Logic - What does ∴ mean in a truth table?

I see the symbol used, and I've never seen it logically defined. In words, It's defined as a symbol meaning 'therefore'. Because of a lack of definition, I have no idea why this is false: ...
1
vote
0answers
40 views

Is this deduction false?

Is this deduction accurate? I have been trying to find out how we can get ~~B by showing contradiction by asssuming A.
1
vote
1answer
23 views

Propositional resolution: the correct way to proceed

I'm trying to solve the following exercise: using resolution, tell whether the following formula can be proven: F = {( L $\wedge$ V) $\rightarrow$ H, L $\rightarrow$ V , L } entails (V $\wedge$ H). ...
0
votes
0answers
12 views

DNF using laws on 3 literals and simplifying

Can someone tell me how to turn this into disjunctive normal form please? For Q1, I find it easy to remove implications, double negations and use distributive law. However I am having a hard time ...
0
votes
1answer
49 views

proof verification for natural deduction in propositional logic

Hi I wanted to know if I got the following natural deduction formula correct. ...
2
votes
2answers
35 views

Compactness theorem, propositional calculus

Please help me with this problem. Prove that if $\land \Phi \models \lor \Psi$ (both $\Phi$ and $\Psi$ infinite) then there exist $\phi_1,...,\phi_n$ from $\Phi$ and $\psi_1,...,\psi_m$ from $\Psi$ ...
0
votes
0answers
27 views

First Order Logic Tableau Multiple Universal Identifiers

I've been looking into tableau lately and I have come across multiple Universal Identifiers which I am not used to. How do I approach these to validate/invalidate with these identifiers and provide an ...
1
vote
1answer
44 views

Resolution method: example

Now i study resolution method over first order logic in university but i can't feel power of this method. Can anyone give such statement that would be at least some nontrivial and interesting and at ...
0
votes
2answers
19 views

Number of truth tables for a 2 letter formula

I am reading a book called "The Haskell Road to Logic, Maths and Programming" A question in the book is: "How many truth tables are there for 2-letter formula's" The answer in the answer sheet is: "...
0
votes
2answers
43 views

Why do some literals disappear when passing from CNF to DNF

$(p \Rightarrow q) \land (q \Rightarrow r) \land \neg(r \Rightarrow p)$ According to wolframalfa the result is $\neg p \land r$. Could you tell me how did this happen? where did $q$ disappear and ...
0
votes
1answer
26 views

Formal Proof in Propositional Logic - Explanation?

Could somebody explain what is happening here? I understood formal proof until the example questions I was reviewing started to include a tick symbol in the answers. The exercise is to write a formal ...
0
votes
2answers
26 views

How can I write a DNF to CNF form?

How can I have write (p∧q) ∨ (¬p ∧ ¬q), which is the equivalent for (p<->q), in conjunctive normal form (CNF)? In general, am I allowed to do (p ∨ (¬p ∧ ¬q)) ∧ (q ∨ (¬p ∧ ¬q)) ??
1
vote
0answers
36 views

How many valuation are there for a set of atoms?

I'm studying propositional logic. On my notebook I wrote: Theorem: If v is a function from ATOMS (set of atoms) into $\{0,1\}$ then exists a unique valuation $[[*]]_v$ such that $[[\psi]]_v=v(\psi)$ ...
2
votes
1answer
44 views

Determining whether a truth function can be defined in terms of another

Given an $n$-ary truth function $f$ and $m$-ary truth function $g$, is there a way to determine whether $g$ can be defined in terms of $f$? In other words, is there a systematic procedure that can ...
0
votes
2answers
53 views

A better general definition of a predicate

What's a better definition for (an interpretation of) a predicate in general (i.e. non-theory-specifically): ...
0
votes
1answer
25 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 ...
1
vote
1answer
37 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: $(\...
2
votes
1answer
41 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 \...
1
vote
2answers
62 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 $(\...
1
vote
1answer
52 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) \...
0
votes
0answers
36 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
30 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
43 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
0answers
34 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 Last(x,...
0
votes
1answer
31 views

proof verification for natural deduction

Could someone please let me know if I got the following natural deduction correct for the following formula ...
3
votes
0answers
57 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
1answer
11 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 ...
0
votes
2answers
52 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 ...
1
vote
2answers
61 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$ ...
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 principles....
0
votes
1answer
27 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
37 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 ...
1
vote
1answer
47 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
4answers
41 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'$ 1, ...
1
vote
2answers
44 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 ...
2
votes
3answers
116 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, ...
0
votes
1answer
112 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
vote
1answer
24 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
18 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
39 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 ...