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)

0
votes
1answer
21 views

Logic Proof using Inference rules and replacement rules

I am trying to prove the following using the inference and replacement rules in logic: (A . F) ⊃ (C ∨ G), ~ (C ∨ (F . G)), F ≡ ~ (X . Y), ~ (X ∨ ~ W) /∴ ~ (A ∨ X) I have this so far: Work But I do ...
0
votes
0answers
27 views

Proving theorems using the Compactness theorem

We say an infinite set $S$ is closed under $\wedge$ if for all $a,b$ $\in S$ so $a\wedge b \in S$. I need to prove that if S is closed under $\wedge$ and for all $a \in S$ we know is that $a$ is ...
1
vote
1answer
155 views

Is ({1, 0}, ⊕, ∨) a field? and Is ({1, 0}, ⊕, ∧) a field?

1 and 0 denote the logical statements True and False. These two questions are for homework so would rather an answer that could help explain it to me then just a straight answer. Thanks to anyone who ...
1
vote
0answers
33 views

Natural Deduction Proof $\neg(P \to Q) \vdash Q \to P$

I am trying to answer Question 3(e) in Exercise 1.2 of Huth and Ryan's Logic in Computer Science book for revision and I am stuck on it. The question asks you to prove the validity of the following ...
1
vote
0answers
16 views

Logic - logical connective for (~ABC) + (A~BC) + (AB~C)?

Is there a logical connective that says 'True, if and only if 1 proposition is true'. Or perhaps even better, is there one that describes 'True, if and only if n propositions is true'? Where n is an ...
1
vote
2answers
27 views

Commas in propositional logic

I want to know what effect a comma has on a propositional statement. For example: $\{\neg p, p \vee q \} \vDash q$ Does this bit $\{\neg p, p \vee q \}$ mean just $q$? Thanks.
2
votes
3answers
72 views

Logical limitations of Proofs by Contradiction

In general proofs by contradiction go as follows: Given an arbitrary hypothesis, $\ p \implies q$, we assume $\left(p\implies q\right) = T$, and then we show that by assuming the hypothesis to be ...
0
votes
1answer
10 views

How to eliminate bi conditionals?

p <--> q can be written as (p → q) ∧ (q → p) (~p V q) Λ (~q V p) After this I am confused. If I distribute Λ over V, I get (~p V q Λ ~q) V (~p V q Λ p) which becomes (~p V q Λ ~q ) V (~p V q ...
1
vote
2answers
72 views

Deducing $((\neg a \to \neg b) \to ((\neg a \to b) \to b)))$ from axioms

I have seen many questions here, using a different set of axioms than mine. Here is mine : $$1) (a \to (b \to a))$$ $$2) ((a \to (b \to c)) \to ((a \to b) \to (a \to c)))$$ $$3) ((\neg b \to \neg a) ...
2
votes
2answers
36 views

Propositional calculus axiom the other way around

I have the following axioms of propositional calculus (as well as modus ponens and the deduction theorem if needed): $$(a \to (b \to a)) \tag1$$ $$ (((a \to (b \to c)) \to ((a \to b) \to (a \to c))) \...
4
votes
1answer
152 views

When does the dual of $s =s$?

Why I believe this is not a duplicate: This question might be the same, but the accepted answer is only a partial answer, because it gives no reason as to why those are the only solutions. Since the ...
1
vote
1answer
42 views

Tarski's schema T

On Wikipedia, Tarski schema T says: A sentence of the form "A and B" is true if and only if A is true and B is true A sentence of the form "A or B" is true if and only if A is true or B is true A ...
0
votes
2answers
48 views

Prove $[(P \lor A) \land ( \neg P \lor B)]\rightarrow (A \lor B)$

I want to prove that $[(P \lor A) \land ( \neg P \lor B)] \rightarrow (A \lor B)$, using distributions or reductions (even though I am aware that simpler proofs exist). The issue is that I keep ...
2
votes
1answer
68 views

Generators of the Lindenbaum-Tarski algebra

I am a bit confused about the role of propositional variables in the construction of the free Lindenbaum-Tarski algebra. In the entry "Lindenbaum-Tarski algebra" on Wikipedia, in the section "...
0
votes
1answer
44 views

Is there a blackboard bold letter for the set of Boolean numbers? [duplicate]

Is there a symbol (e.g. $\mathbb{B}$) for the special set of Boolean numbers or values; ${0,1}$ or ${True,False}$?
0
votes
0answers
17 views

Mathematical logic: Predicates, formula

I've got universum $A = \{0,1,2\}$ Predicate: $R^{A}=\{\{x,y\} \in A \times A \hspace{2mm} | \hspace{2mm} x \neq y \} $ Terms: $f^A(x) = 1$ $g^A(x,y) = min(x,y)$ Constant $c^A = 2$ Valuation: $...
2
votes
0answers
66 views

Are these two logical statements equal?

I found this question from a website: "Neither the fox nor the lynx can catch the hare if the hare is alert and quick." Let: P: The fox can catch the hare Q: The lynx can catch ...
0
votes
1answer
31 views

Prove or disprove in propositional calculus

I have the following question - and would like to make clear some definition via it's answer - Prove of Disprove - If $\\X\models\alpha$ and $\\Y\models\alpha$, then $X\cap Y\models\alpha$ ...
1
vote
0answers
20 views

From Propositional Calculus Proof to Predicate Calculus Proof

PROVE: If {$\Delta_{i}$} are all deductively closed set of formulae, so is $\cap \Delta_i$. Show with predicate Calculus. Definition: {$\Delta_{i}$} a set $\Delta$ of formulae is deductively closed ...
3
votes
0answers
41 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
41 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
41 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
16 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
44 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
47 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
40 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
18 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
42 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
25 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
25 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
32 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
50 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
29 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 ...