This is the truth table for nand.
We can express negation using nand:
We can express conjunction (and) using nand. We can use plain old negation, since we already know how to encode it just using nand.
We can now express disjunction (or) using nand. Again, we also use negation and conjunction since we know how to express them.
We have already shown that we can express and and or with nand. So it is enough to show that xor can be expressed with and and or to prove that we can only express it with nand.
Another elementary operation like nand is nor. It is if and otherwise.
In total, there are 16 different possibilities for boolean functions with two arguments: Since takes two arguments, each of which can be either or , there are exactly possible different inputs. For each of these inputs there are 2 different possible results: and . This means in total we can find functions. All of functions can be represented only using and, or, and negation, as follows:
Now that we have shown that every boolean function with two arguments can be represented with and, not, and or and that we have shown in exercise 6 that and and or can be expressed with nand, the only thing left to show is that not can also be expressed using only nand.
In conclusion, we have now shown that and, or and not can be expressed using only nand, because we have also shown that every boolean function with two arguments can be represented by and, or and not we can conclude that nand is universal.
or alternatively
unsigned int f1(unsigned int n, unsigned int k) {
assert(k < 32);
unsigned int a = 1 << k;
return n ^ a;
}
unsigned int f2(unsigned int n, unsigned int k) {
assert(k < 32);
unsigned int a = 1 << k;
return n | a;
}
unsigned int f3(unsigned int n, unsigned int k) {
assert(k < 32);
unsigned int a = (unsigned int)1 << k;
return n & ~a;
}
unsigned int f4(unsigned int n, unsigned int k) {
assert(0 < k && k < 32);
unsigned int s = 32;
return (n << k) | (n >> (s - k));
}
unsigned int f5(unsigned int n, unsigned int k)
{
assert(0 < k && k < 32);
unsigned int s = 32;
return (n << (s - k)) | (n >> k);
}
#include <stdio.h>
int caesar(char* text, int n) {
if (n > 25 || n < 0) {
printf("The value of n needs to be between 0 and 25 (was %i)", n);
return 1;
}
while (*text != '\0') {
// shift
*text += n;
// fix shifting boundary violations
if (*text > 'z') {
*text = *text - 'z' + 'a' - 1;
}
text++;
}
return 0;
}
int main() {
int shift = 5;
char text[] = "abcdz";
printf("Plain text:\n");
printf("%s\n", text);
printf("Shift by %i\n", shift);
int ret = caesar(text, shift);
if (ret == 0) {
printf("Cipher:\n");
printf("%s\n", text);
}
return ret;
}
#include <stdio.h>
int main(int argc, char* argv[])
{
// declare pointers to int objects
int *dr, *ds;
// declare pointers to pointers to int objects
int **drr, **dss;
int i;
// declare an array of 5 ints
int aa[5];
// set every array element to -123
for (i = 0; i < 5; i++) *(aa + i) = -123;
// dr is assigned the address of aa's fourth element: dr-->aa[3]
dr = &aa[3];
// ds is assigned the address of aa's first element: dr-->aa[0]
ds = dr - 3;
// drr now points to dr: drr-->dr-->aa[3]
drr = &dr;
// dss now points to ds: dss-->ds-->aa[0]
dss = &ds;
// the container pointed to by dr is set to 23: aa[3] = 23
*dr = 23;
// the container pointed to by ds is set to 11: aa[0] = 11
*ds = 11;
// the container behind the one pointed to by dr is set to 5: aa[3+1] = 5
*(dr + 1) = 5;
// ds now points to the next array element: dss-->ds-->aa[1]
ds += 1;
// the container pointed to by ds is set to 66: a[1] = 66
*ds = 66;
aa[2] = 42;
// Output: 11 66 42 23 5
printf("%d %d %d %d %d\n", aa[0], aa[1], aa[2], aa[3], aa[4]);
// a[0] = aa[2] - aa[1] = 42-66 = -24
aa[0] = *(aa+2) - *(aa + 1);
// the container before the one pointed to by dr is set to 7: a[3-1] = 7
*(*drr - 1) = 7;
// The content of the third container behind ds is set to 4: a[1+3] = 4
*(*dss + 3) = 4;
// aa[1] = aa[3] + a[3-2] = 23+66 = 89
**dss = **drr + *(*drr - 2);
// Output: -24 89 7 23 4
printf("%d %d %d %d %d\n", aa[0], aa[1], aa[2], aa[3], aa[4]);
return 0;
}#include <stdlib.h>
#include <assert.h>
#include "poly.h"
struct poly_t {
unsigned degree;
int *coeffs;
};
poly_t *poly_alloc(unsigned degree) {
poly_t *p = malloc(sizeof(*p));
p->degree = degree;
p->coeffs = malloc((degree + 1)
* sizeof(p->coeffs[0]));
return p;
}
void poly_free(poly_t *p) {
free(p->coeffs);
free(p);
}
void poly_set_coeff(poly_t *p, unsigned i,
int val) {
assert(i <= p->degree);
p->coeffs[i] = val;
}
int poly_eval(poly_t const *p, int x) {
int res = p->coeffs[0];
for (unsigned i = 1; i <= p->degree; i++)
res = res * x + p->coeffs[i];
return res;
}
struct list_node_t {
int element;
struct list_node_t* prev;
struct list_node_t* next;
};
typedef struct list_node_t list_node_t;
list_node_t* list_root_init(list_node_t** head, list_node_t** tail) {
*head = NULL;
*tail = NULL;
}
list_node_t* list_prepend_at_head(list_node_t** head, list_node_t** tail,
int element) {
list_node_t* n = malloc(sizeof(*n));
n->element = element;
n->prev = NULL;
n->next = *head; // no matter whether `*head == NULL`
if (*head != NULL) {
(*head)->prev = n;
} else { // list was empty, now singleton
assert(*tail == NULL);
*tail = n;
}
*head = n; // no matter whether `*head == NULL`
return n;
}
list_node_t* list_append_at_tail(list_node_t** head, list_node_t** tail,
int element) {
list_node_t* n = malloc(sizeof(*n));
n->element = element;
n->prev = *tail; // no matter wheter `*tail == NULL`
n->next = NULL;
if (*tail != NULL) {
(*tail)->next = n;
} else { // list was empty, now singleton
assert(*head == NULL);
*head = n;
}
*tail = n;
return n;
}
list_node_t* list_prepend_at(list_node_t** head, list_node_t** tail,
list_node_t* where, int element) {
if (where->prev == NULL) { // where == *head
return list_prepend_at_head(head, tail, element);
} else {
list_node_t* n = malloc(sizeof(*n));
n->element = element;
n->prev = where->prev;
n->next = where;
where->prev = n;
where->prev->next = n;
return n;
}
}
list_node_t* list_append_at(list_node_t** head, list_node_t** tail,
list_node_t* where, int element) {
if (where->next == NULL) { // where == *tail
return list_append_at_tail(head, tail, element);
} else {
return list_prepend_at(head, tail, where->next, element);
}
}
void list_remove(list_node_t** head, list_node_t** tail, list_node_t* n) {
if (n->prev != NULL) {
n->prev->next = n->next;
} else { // n = *head
*head = n->next;
}
if (n->next != NULL) {
n->next->prev = n->prev;
} else { // n = *tail
*tail = n->prev;
}
free(n);
}head and tail pointers in this one. But there the first and last list element have pointers to the dummy node, thus it is accessible from within the list. This is not the case when the first and last elements point to NULL, so we have to pass them as double pointers to be able to change them appropriately.list_prepend_at_head and prepending to the dummy node is equivalent to list_append_at_tail. Without (one of) these functions it would not be possible to add the first element to an empty list.We first prove the dual formulation of the above statement:
To do this, we introduce the minimal size of a balanced tree of height as .
: The tree is a single node.
: The tree is either a root with a single child or a root node with two children. The first case has less nodes, so we define: .
:
By the definition of height, one subtree has height . Using proof by contradiction, we can show that the other subtree has height as the size would not be minimal otherwise. By recursion, we obtain the minimal sized trees for and .
By definition of , we have for every tree of size and height , .
We show to obtain by transitivity.
By complete induction on :
:
:
:
:
Induction hypothesis:
Lastly, we obtain from the inequality .