Reduce a huge number of possibilites to something manageable? I have this problem, which seems like it should have an easy solution, but I can't figure it out.

Say we have pizza_toppings table where a chef enters available sets of toppings. There are four toppings: pepperoni, olives, pepper, and basil. The chef makes four different pizzas with the above ingredients:

pizza_toppings
--------------
pizza 1 has only pepperoni
pizza 2 has pepperoni and olives
pizza 3 has olives or basil
pizza 4 has ( pepperoni and pepper) or only basil


How would I record all these 'and', 'or', 'and + or', 'and + and', '(and + or) + and ...', etc. relationships between table entries?

It seems like a problem from some difficult textbook that should have a clever solution, which I can't figure out. My program doesn't actually deal with pizza and there will be countless "toppings" created by users and infinite possible combinations, which will also be combined by users. So I can't really make a table with pre-defined combinations. Is there a solution to such a problem?
Hmmm... interesting question. 

As you say, you can have hundreds even thousands of different combinations of toppings, but you don't want a menu the length of 'War and Peace'. 

I would divide the toppings into categories (cat_1... cat_5) and have your pizza price based on the top 3 categories on your pizza. 


1€ for cat_1 (salami, anchovies), 
75¢ for cat_2 (turkey, chicken), 
50¢ for cat_3 (pineapple, porcini), 
25¢ for cat_4 (capers, cherry tomato)
0¢ for cat_5 (x 2 - standard tomato, mushroom)


So, you have a base price of, say, 5€ per pizza, then add two cat_1 and a cat_3 topping for a total price of €7.75. 

Allow two "standard" toppings - say tomato and cheese as cat_5 and you have a relatively simple pricing scheme that even the stupidest staff member or client can understand.

You could also provide "specials" from time to time - i.e. "Normally, €7.50 - try it tonight for €6.50..." or suchlike!

You appear to be suggesting that pizzas are not your prime focus in life? Maybe if you explained your requirements in further detail, we might be able to be of more assistance. Having said that, I think the scheme above or similar would go a long way to helping resolve this or similar issues.

On a database level, I would have something like the following (fiddle):

CREATE TABLE order_
(
  order_id serial NOT NULL,
  order_time timestamp NOT NULL,
  order_taken_by INTEGER NOT NULL, -- references employee table
  order_served_by INTEGER NOT NULL, -- same
  order_value INTEGER NOT NULL -- in cent
);

CREATE TABLE order_item
(
  order_item_id SERIAL NOT NULL,  -- may be pizza_id
  order_item_price INTEGER NOT NULL
);

CREATE TABLE pizza
(
  pizza_id serial NOT NULL,
  cat_1_items VARCHAR (50), -- references table of cat_1 toppings
  cat_2_items VARCHAR (50) -- cat_2 toppings
  -- ..
  -- ..
  -- ..
);


You might have a stored procedure to calculate your pizza price? You might also find this interesting.